【刷题day20】二叉树|654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树

654. 最大二叉树

凡是构造二叉树类的题目，我们都要用前序遍历

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) 
            return nullptr;
        //找到数组中最大值对应的下标
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex]) 
                maxValueIndex = i;
        }
        TreeNode* root = new TreeNode(nums[maxValueIndex]);
        root->left = traversal(nums, left, maxValueIndex);
        root->right = traversal(nums, maxValueIndex + 1, right);
        return root;
    }
};

617. 合并二叉树

一起处理两个二叉树，其实和操作一个在递归中是一样的

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }

700. 二叉搜索树中的搜索

二叉搜索树是有一些特性的，左孩子<根节点<右孩子

TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) 
            return root;
        TreeNode* result = NULL;
        if (root->val > val) 
            result = searchBST(root->left, val);
        if (root->val < val) 
            result = searchBST(root->right, val);
        return result;
    }

98. 验证二叉搜索

二叉搜索树的中序遍历是有序的

注意：根节点要比左子树，不仅仅是左孩子，都要大。根节点要比右子树，不仅仅是右孩子，都要小

TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) 
            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;
    }