网站的投票 计数模块怎么做,阿里云申请域名后网站,中国建设银行网站医保,互联网网站建设趋势非科班学习算法day21 | LeetCode669:修剪二叉搜索树 #xff0c;Leetcode108:将有序数组转换为二叉搜索树 #xff0c;Leetcode538:把二叉搜索树转换为累加树 介绍
包含LC的两道题目#xff0c;还有相应概念的补充。
相关图解和更多版本#xff1a;
代码随想录 (progra… 非科班学习算法day21 | LeetCode669:修剪二叉搜索树 Leetcode108:将有序数组转换为二叉搜索树 Leetcode538:把二叉搜索树转换为累加树 介绍
包含LC的两道题目还有相应概念的补充。
相关图解和更多版本
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF 二、LeetCode题目
1.LeetCode669:修剪二叉搜索树
题目链接669. 修剪二叉搜索树 - 力扣LeetCode 题目解析 这道题第二次做一开始还是迷糊其实本质还是删除节点只不过我们需要直到不能看到没在范围的就直接删除因为其子树也是有大有小的所以就要处理相应的节点。那就是在下限之下向右边遍历在上限之上向左边遍历。同时对于节点的拼接处理就是去掉一半子树。思路想清楚代码看起来还是比较简洁。 c代码如下
/*** 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 {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(!root) return nullptr;if(root-vallow){return trimBST(root-right, low,high);}if(root-val high){return trimBST(root-left,low,high);}root-left trimBST(root-left,low,high);root-right trimBST(root-right,low,high);return root;}
}; 2.Leetcode108:将有序数组转换为二叉搜索树
题目链接108. 将有序数组转换为二叉搜索树 - 力扣LeetCode 题目解析 一开始还在想是不是需要将奇偶分类实际上没有必要因为有平衡的要求也不用慌因为最中间的两个值用左边和右边构造是一样的。这里就采用中间左边构造的形式。 需要理清思路每层选取最中间的数作为根节点有点像之前根据遍历顺序构造数的做法。想清楚这个之后代码才能好写起来。 C代码如下
/*** 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 {
public:TreeNode* sorted(vectorint nums, int left, int right) {if(leftright) return nullptr;int mid left (right - left) / 2;TreeNode* root new TreeNode(nums[mid]);root-left sorted(nums, left, mid - 1);root-right sorted(nums, mid 1, right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {return sorted(nums, 0, nums.size() - 1);}
}; 注意点因为要整个遍历且返回值是作为对应根节点的孩子节点接住的所以直接用root-left
3.Leetcode538:把二叉搜索树转换为累加树
题目链接538. 把二叉搜索树转换为累加树 - 力扣LeetCode 题目解析 一眼看上去也是构造树不过这道题不需要动节点只需要返回节点的值进行运算就可以这里也是用回溯的思想。先遍历右边将右边的值返回中做处理就是相加最后遍历左边。这样就符合了累加树的计算方法 C代码如下
/*** 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 {
public:// 尝试右中左遍历int sum 0;TreeNode* convertBST(TreeNode* root) {if (!root)return nullptr;convertBST(root-right);sum root-val;root-val sum;convertBST(root-left);return root;}
};
注意点1只是提供了一种新的思路面对二叉树要灵活把已经做过的看看能不能用上。 总结 补打卡第21天坚持
