做游戏网站需求确认,站内推广途径,如何建设门户网站,湖南长沙防控指挥部最新公告文档讲解#xff1a;最大二叉树 合并二叉树 二叉搜索树中的搜索 验证二叉搜索树 654.最大二叉树
题目链接#xff1a;https://leetcode.cn/problems/maximum-binary-tree/description/
思路#xff1a; 本题目要求我们根据已知数组构建一颗最大二叉树#xff0c;最大值… 文档讲解最大二叉树 合并二叉树 二叉搜索树中的搜索 验证二叉搜索树 654.最大二叉树
题目链接https://leetcode.cn/problems/maximum-binary-tree/description/
思路 本题目要求我们根据已知数组构建一颗最大二叉树最大值为根节点最大值左边区间构建左子树最大值右边区间构建右子树。 很容易我们就能想到这道题目要用递归来实现因为针对每个区间我们的操作都是相同的先寻找最大值构建根节点再分割左右区间构建左右子树。因此我们对总区间 [0,n-1] 进行递归处理递归边界条件为 lr-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(vectorint nums,int l,int r){if(lr||l0||rnums.size()) return NULL;int maxvall;for(int il;ir;i)if(nums[i]nums[maxval]) maxvali;TreeNode* curnew TreeNode(nums[maxval]);cur-leftcreateTree(nums,l,maxval);cur-rightcreateTree(nums,maxval1,r);return cur;}
public:TreeNode* constructMaximumBinaryTree(vectorint 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-valcur2-val;cur1-leftmerge(cur1-left,cur2-left);cur1-rightmerge(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-valval) return cur;else if(cur-valval) 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 flagtrue;vectorint isValid(TreeNode* cur){vectorint nums;int minnumcur-val,maxnumcur-val;if(cur-left){vectorint numlisValid(cur-left);if(numl[0]minnum) minnumnuml[0];if(numl[1]maxnum) maxnumnuml[1];if(numl[1]cur-val){flagfalse;}}if(cur-right){vectorint numrisValid(cur-right);if(numr[0]minnum) minnumnumr[0];if(numr[1]maxnum) maxnumnumr[1];if(numr[0]cur-val){flagfalse;}}nums.push_back(minnum);nums.push_back(maxnum);return nums;}
public:bool isValidBST(TreeNode* root) {isValid(root);return flag;}
};
今日总结 今日学习时长2h题目不算难但我的解法不算好肯定有更好的解法还没来得及看因为这两天又要准备期末先把期末过了再说。
