代码随想录算法训练营29期Day20|LeetCode 654,617,700,98

发布时间:2024年01月15日

???文档讲解:最大二叉树??合并二叉树??二叉搜索树中的搜索??验证二叉搜索树

654.最大二叉树

题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/

思路:

? ? ? ? 本题目要求我们根据已知数组构建一颗最大二叉树,最大值为根节点,最大值左边区间构建左子树,最大值右边区间构建右子树。

? ? ? ? 很容易我们就能想到这道题目要用递归来实现,因为针对每个区间我们的操作都是相同的:先寻找最大值构建根节点,再分割左右区间构建左右子树。因此我们对总区间 [0,n-1] 进行递归处理,递归边界条件为 l==r-1 ,即区间中只有一个点,这时就到达了叶子节点,不用再向下构建了,挨层回溯子树根节点即可,最后总区间回溯出的节点就是整颗树的根节点。

核心代码:

/**
 * 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 {
private:
    TreeNode* createTree(vector<int>& nums,int l,int r){
        if(l>=r||l<0||r>nums.size()) return NULL;
        int maxval=l;
        for(int i=l;i<r;i++)
          if(nums[i]>nums[maxval]) maxval=i;
        TreeNode* cur=new TreeNode(nums[maxval]);
        cur->left=createTree(nums,l,maxval);
        cur->right=createTree(nums,maxval+1,r);
        return cur;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return createTree(nums,0,nums.size());
    }
};

617.合并二叉树

题目链接:https://leetcode.cn/problems/merge-two-binary-trees/description/

思路:

? ? ? ? 本题要求我们将两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为?null 的节点将直接作为新二叉树的节点。

? ? ? ? 我们从根节点开始,考虑每个节点的情况,分别处理即可,分析以后会发现很简单。

? ? ? ? 我们先假设两棵树为树1和树2,当前处理到的位置相同的点为cur1和cur2,其中cur1为树1的节点,cur2为树2的节点。下面我们分类讨论:

? ? ? ? 1.如果cur1和cur2都是空节点,那么新树中这个点必定为空,就不用向下处理了,向下肯定也是空的,因为下面已经没有点了。

? ? ? ? 2.如果cur1是空节点,cur2不是空节点,那么新树中以当前位置这个点为根节点的子树,其构造必定和树2中以cur2为根节点的子树完全一致,因为cur1是空的,那么树1以cur1为根节点的子树也必定为空,那就不会向cur2那颗子树合并,或者说合并后还是cur2那颗子树,所以我们返回cur2即可,也不必再向下构造了。

? ? ? ? 3.如果cur1不是空节点,cur2是空节点,那么这种情况与2重复,同样的处理方式即可,不过这次返回的是cur1这棵子树,或者说树1的cur1节点。

? ? ? ? 4.如果cur1和cur2都不是空节点,那么我们将其值合并,变成新节点赋给新树对应位置节点,然后分别递归处理左右儿子,左右儿子的情况又回到这四种情况中,判断是哪种情况处理即可。

核心代码:

/**
 * 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 {
    TreeNode* merge(TreeNode* cur1,TreeNode* cur2){
        if(!cur1&&!cur2) return NULL;
        if(!cur1) return cur2;
        if(!cur2) return cur1;
        cur1->val+=cur2->val;
        cur1->left=merge(cur1->left,cur2->left);
        cur1->right=merge(cur1->right,cur2->right);
        return cur1;
    }
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return merge(root1,root2);
    }
};

700.二叉搜索树中的搜索

题目链接:https://leetcode.cn/problems/search-in-a-binary-search-tree/description/

思路:

? ? ? ?本题要求我们在 BST 中找到节点值等于?val?的节点。 返回以该节点为根的子树。 如果节点不存在,则返回?null?。

? ? ? ? 思路也很简单,递归向下搜索即可。每次判断当前节点的值与val的大小关系,如果val大,就向右子树去搜,如果val小,就向左子树去搜,搜到空节点或者值相等为止。值相等证明找到了,返回当前节点,空节点证明树中没有该值,返回空即可。

核心代码:

/**
 * 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 {
private:
    TreeNode* searchval(TreeNode* cur,int val){
        if(!cur) return NULL;
        else if(cur->val==val) return cur;
        else if(cur->val>val) return searchval(cur->left,val);
        else return searchval(cur->right,val);
    }
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        return searchval(root,val);
    }
};

98.验证二叉搜索树

题目链接:https://leetcode.cn/problems/validate-binary-search-tree/description/

思路:

? ? ? ? 本题目要求我们判断一棵树是否是一个有效的二叉搜索树。

? ? ? ? 首先我们要知道,所谓的有效的二叉搜索树,就是说针对树中任意非空节点作为根节点来说,左子树的最大值小于根节点值,右子树的最小值大于根节点值。因此我们从根节点开始递归的处理每棵子树即可。

? ? ? ? 我们可以开一个全局变量flag,记录整颗树是否合法。也就是递归的时候处理到不合法情况让flag值为false即可。递归结束后flag为true证明整颗树合法,反之则不合法。flag初始值为true。

????????每层递归我们要做的事情如下:递归处理左子树的最大值和最小值,递归处理右子树的最大值和最小值。得到这四个值结合根节点值我们就可以判断整颗树是否合法,从而决定flag是否为false。同时我们可以得到整颗树的最小值和最大值,向上一层回溯这两个值即可。

????????注意递归的边界条件为左右儿子均为空节点,即当前子树只有一个节点,就是总树的叶子节点,这时子树的最大值和最小值相同,均为子树根节点值。

核心代码:

/**
 * 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 {
private:
    bool flag=true;
    vector<int> isValid(TreeNode* cur){
        vector<int> nums;
        int minnum=cur->val,maxnum=cur->val;
        if(cur->left){
            vector<int> numl=isValid(cur->left);
            if(numl[0]<minnum) minnum=numl[0];
            if(numl[1]>maxnum) maxnum=numl[1];
            if(numl[1]>=cur->val){
                flag=false;
            }
        }
        if(cur->right){
            vector<int> numr=isValid(cur->right);
            if(numr[0]<minnum) minnum=numr[0];
            if(numr[1]>maxnum) maxnum=numr[1];
            if(numr[0]<=cur->val){
                flag=false;
            }
        }
        nums.push_back(minnum);
        nums.push_back(maxnum);
        return nums;
    }
public:
    bool isValidBST(TreeNode* root) {
        isValid(root);
        return flag;
    }
};

今日总结

????????今日学习时长2h,题目不算难,但我的解法不算好,肯定有更好的解法,还没来得及看,因为这两天又要准备期末,先把期末过了再说。

文章来源:https://blog.csdn.net/tlingyuqi/article/details/135591132
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。