654.最大二叉树

蛮简单的，逻辑跟构造树基本一致

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            if(nums.size() == 0) return nullptr;
            pair<int,int> root;
            root.first = INT_MIN; //root->val
            root.second = 0;  //root index
            for(int i = 0; i < nums.size(); ++i){
                if(nums[i] > root.first){
                    root.first = nums[i];
                    root.second = i;
                }
            }
            TreeNode* rootnode = new TreeNode(root.first);
            vector<int> left(nums.begin(),nums.begin() + root.second);
            vector<int> right(nums.begin() + root.second + 1, nums.end());
            rootnode->left = constructMaximumBinaryTree(left);
            rootnode->right = constructMaximumBinaryTree(right);
            return rootnode;
    }
};

注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
优化版本：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructTree(nums,0,nums.size());
    }
    TreeNode* constructTree(vector<int>& nums,int left,int right) {
        if(left >= right) return nullptr;
        int index;
        int maxnum = INT_MIN;
        for(int i = left; i < right; ++i){
            if(nums[i] > maxnum){
                maxnum = nums[i];
                index = i;
            }
        }
        TreeNode* root = new TreeNode(maxnum);
        root->left = constructTree(nums,left, index);
        root->right = constructTree(nums,index+1,right);
        return root;
    }
};

617.合并二叉树

跟遍历一棵树是一样的，只不过要处理两棵树同一个地方的节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return nullptr;
        else if(root1 != nullptr && root2 == nullptr) return root1;
        else if(root1 == nullptr && root2 != nullptr) return root2;
        
        int val = root1->val + root2->val;
        TreeNode* root = new TreeNode(val);
        
        root->left = mergeTrees(root1->left,root2->left);
        root->right = mergeTrees(root1->right,root2->right);

        return root;
    }
};

700.二叉搜索树中的搜索

二叉搜索树是一个有序树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

递归法：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr || root->val == val) return root;

        TreeNode* res = nullptr;
        if(root->val > val) res = searchBST(root->left,val);
        if(root->val < val) res = searchBST(root->right,val);
        
        return res;
    }
};

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

98.验证二叉搜索树

如果按照中序遍历，并且当前元素不大于上一个，就返回false的逻辑。是有漏洞的。没有考虑到只有一个或两个（中，左）节点的情况。
所以只能全部遍历，然后和前一个元素作比较

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        vec.clear();
        chek(root, vec);
        for(int i = 1; i < vec.size(); ++i){
            if(vec[i] <= vec[i-1]) return false;
        }
        return true;
    }
    void chek(TreeNode* root,vector<int>& vec){
        if(root == nullptr) return; 
        chek(root->left,vec);
        vec.push_back(root->val);
        chek(root->right,vec);
    }
};