day17 二叉树5

654.最大二叉树

class Solution {
public:
    int getMaxIndex(vector<int> &nums, int left, int right) {
        int index = left;
        for (int i = left + 1; i < right; i ++) {
            if (nums[i] > nums[index]) {
                index = i;
            }
        }
        return index;
    }

    TreeNode *traversal(vector<int> &nums, int left, int right) {
        if (left >= right) {
            return nullptr;
        }
        int index = getMaxIndex(nums, left, right);
        TreeNode *node = new TreeNode(nums[index]);
        node->left = traversal(nums, left, index);
        node->right = traversal(nums, index + 1, right);
        return node;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

617.合并二叉树

class Solution {
public:
    TreeNode* merge(TreeNode* node1, TreeNode *node2) {
        if (node1 == nullptr) {
            return node2;
        }
        if (node2 == nullptr) {
            return node1;
        }
        TreeNode *res = new TreeNode(node1->val + node2->val);
        res->left = merge(node1->left, node2->left);
        res->right = merge(node1->right, node2->right);
        return res;
    }

    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return merge(root1, root2);
    }
};

700.二叉搜索树中的搜索

迭代法：

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

递归法：

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);
        }
        else {
            res = searchBST(root->right, val);
        }
        return res;
    }
};

98.验证二叉搜索树

递归法中序遍历

class Solution {
public:
    long maxVal = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        bool left = isValidBST(root->left);
        if (maxVal < root->val) {
            maxVal = root->val;
        }
        else {
            return false;
        }
        bool right = isValidBST(root->right);
        return left && right;
    }
};