654.最大二叉树

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    // 构造二叉树，都需要用到前序，中左右
        if (nums.size() == 1) {
            return new TreeNode(nums[0]);
        }
        int index = 0;
        int MaxValue = 0;
        // 找到最大值 (中)
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > MaxValue) {
                MaxValue = nums[i];
                index = i; // 记录此时最大值索引
            }
        }
        TreeNode* node = new TreeNode(MaxValue);

        // (左) 左边最少需要有一个元素
        if (index > 0) {
            vector<int> NewVector(nums.begin(), nums.begin() + index);
            node->left = constructMaximumBinaryTree(NewVector);
        }

        // (右) 右边也需要最少一个元素
        if (index < nums.size() - 1) {
            vector<int> NewVector(nums.begin() + index + 1, nums.end());
            node->right = constructMaximumBinaryTree(NewVector);
        }

        return node;
    }
};

617.合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr) return root2;
        if (root2 == nullptr) return root1;

        TreeNode* root = new TreeNode(0);
        // 前序
        // 中
        root->val = root1->val + root2->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;
        // 左
        if (root->val > val) return searchBST(root->left, val);
        // 右
        if (root->val < val) return searchBST(root->right, val);
        return NULL;
    }
};

98.验证二叉搜索树

非最优，但思路简单

class Solution {
public:
    // 二叉搜索树，中序遍历，是有序的
    void GetVector(TreeNode* node, vector<int>& vec) {
        if (node == nullptr) return;
        if (node->left) GetVector(node->left, vec);
        vec.push_back(node->val);
        if (node->right) GetVector(node->right, vec);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        GetVector(root, vec);
        for (int i = 0; i < vec.size() - 1; i++) {
            if (vec[i] >= vec[i+1]) return false;
        }
        return true;
    }
};

最优解，直接在遍历过程中，使用双指针比较大小。

class Solution {
public:
    // 记录前一个节点
    TreeNode* pre = NULL;

    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        // 左
        bool left = isValidBST(root->left);
        // 中
        if (pre !=NULL && pre->val >= root->val) return false;
        pre = root;
        // 右
        bool right = isValidBST(root->right);
        return left && right;
    }
};