算法刷题 Day 20 | 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

今日内容

• 最大二叉树
• 合并二叉树
• 二叉搜索树中的搜索
• 验证二叉搜索树

详细布置

654.最大二叉树

又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历

题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

Tips：需要注意的是，创建新的node对象时一定要用构造函数。

我的题解：

class Solution {
public:
    TreeNode* construct(vector<int>& nums, int left, int right){
        if(left == right){
            return NULL;
        }
        TreeNode* node = new TreeNode();
        if(right - left == 1){
            node->val = nums[left];
            return node;
        }

        int maxVal = INT_MIN;
        int maxPos = left;
        for(int i = left; i < right; i++){
            if(nums[i] > maxVal){
                maxVal = nums[i];
                maxPos = i;
            }
        }
        node->val = maxVal;
        node->left = construct(nums, left, maxPos);
        node->right = construct(nums, maxPos+1,right);
        return node;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size()==0){
            return NULL;
        }
        return construct(nums, 0, nums.size());
    }
};

617.合并二叉树

这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。

题目链接/文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

Tips：这里的思想是不用什么东西都新建一个，可以用已有的对象来节约内存。同时如果有一个为NULL的话直接返回另一个就行（如果另一个也是NULL，那返回的就是NULL），不用接着向下再进行操作了，也能节省很多时间。

我的题解：

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

        root1->val = root1-> val + root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

700.二叉搜索树中的搜索

递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性

题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

Tips：

我的题解：

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

98.验证二叉搜索树

遇到 搜索树，一定想着中序遍历，这样才能利用上特性。

但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。

题目链接/文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

Tips：

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

我的题解：

1. 数组法：

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& vec){
        if(root == NULL){
            return;
        }

        traversal(root->left,vec);
        vec.push_back(root->val);
        traversal(root->right,vec);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        traversal(root, vec);

        for(int i = 1; i<vec.size();i++){
            if(vec[i] <= vec[i - 1]){
                return false;
            }
        }
        return true;
    }
};

2. 直接递归法

class Solution {
public:
    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;
    }
};