南京建设工程交易中心,江东怎样优化seo,商丘市建设,wordpress设置标题字体文章目录 Day 2301. 修剪二叉搜索树#xff08;No. 669#xff09;1.1 题目1.2 笔记1.3 代码 02. 将有序数组转换为二叉搜索树#xff08;No. 108#xff09;2.1 题目2.2 笔记2.3 代码 03. 把二叉搜索树转换为累加树#xff08;No. 538#xff09;3.1 题目3.2 笔记3.3 代… 文章目录 Day 2301. 修剪二叉搜索树No. 6691.1 题目1.2 笔记1.3 代码 02. 将有序数组转换为二叉搜索树No. 1082.1 题目2.2 笔记2.3 代码 03. 把二叉搜索树转换为累加树No. 5383.1 题目3.2 笔记3.3 代码 Day 23
01. 修剪二叉搜索树No. 669
题目链接
代码随想录题解
1.1 题目
给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
示例 1 输入root [1,0,2], low 1, high 2 输出[1,null,2] 示例 2 输入root [3,0,4,null,2,null,null,1], low 1, high 3 输出[3,2,null,1] 提示
树中节点数在范围 [1, 104] 内0 Node.val 104树中每个节点的值都是 唯一 的题目数据保证输入是一棵有效的二叉搜索树0 low high 104
1.2 笔记
在解这道题之前先来看一段代码
public TreeNode traversal(root) {if (root null) {return null;}root.left traversal(root.left);root.right traversal(root.right);return root;
}这段代码实现了什么呢 根据递归来分析 递归的出口root null递归的返回值以及其用途返回的是当前节点经过处理后的值将其作为上个节点的左子树或者右子树对每个节点的操作分别向左递归返回左子树向右递归返回右子树。 最终可以分析得出上面的代码就是没有做任何的操作只是将左子树赋给左子树将右子树赋值给右子树。 ❓ 很多朋友看到这里可能怀疑我脑子坏掉了为什么要举这么无意义的例子呢 其实换个思路去想将左子树赋值给左子树相当于没做任何操作那如果在递归中进行一些操作使得这个返回值不是左子树而是左子树的下的节点那不就完成了节点的删除吗 那这道题的思路就清晰了一些对于不处于规定范围内的节点在递归的过程中去改变返回的值使得其上个节点得到的是修剪后的子树但对于处于范围内的节点则负责接收修改的左子树和右子树。
那这样递归的框架就能很容易的写出来写出来
public TreeNode traversal(TreeNode root, int low, int high) {if (root null) {}if (root.val high) {} else if (root.val low) {} else {root.right traversal(root.right, low, high);root.left traversal(root.left, low, high); return root;}}先确定了返回值送分题root null因为对空节点的任何操作都没有意义。然后对该节点不处于规定范围和处于规定范围做不同的处理。对于处于规定范围的节点直接负责接收值。 然后来看这个具体的案例来思考如果节点处于范围外应该去做些什么回想一下上面提到的修剪其实就是让本节点的返回值不再是它自己而是它的符合情况的子树 节点 0 是在范围外的所以它的右子树可能在范围内所以这里返回的就是它的向右递归搜索的结果思考到这里就可以了递归一定不要去特别深入的思考否则很容易将自己绕进去 这里理顺这个关系就可以首先要去返回它符合条件子树来达到修剪的目的而符合条件的子树肯定是出现在该节点的右子树然后在右子树中去执行相同的逻辑那调用这个方法最终返回的结果就是符合规范的子树。 比如 0 节点返回的就是 1 2 这个子树 return traversal(root.right);那对于 root.val high 的处理情况也很清晰了要去它 左子树 去得到符合规范的子树。
return traversal(root.left)k将上面的代码补充完整。
1.3 代码
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root null) {return null;}if (root.val high) {return trimBST(root.left, low, high);} else if (root.val low) {return trimBST(root.right, low, high);} else {root.right trimBST(root.right, low, high);root.left trimBST(root.left, low, high); return root;}}
}02. 将有序数组转换为二叉搜索树No. 108
题目链接
代码随想录题解
2.1 题目
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1 输入nums [-10,-3,0,5,9] 输出[0,-3,9,-10,null,5] 解释[0,-10,5,null,-3,null,9] 也将被视为正确答案 示例 2 输入nums [1,3] 输出[3,1] 解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 提示
1 nums.length 104-104 nums[i] 104nums 按 严格递增 顺序排列
2.2 笔记
延续上一道题其实构造一个二叉树无非也就是这样的思路
首先将这个节点创造出来然后分别向两侧去遍历使得返回值是构造好的子树并且将这个子树置于其左子树和右子树即可。
先来写一个基础的结构
public TreeNode traversal(int[] nums, int startIndex, int endIndex) {if () {// 终止条件}TreeNode node new TreeNode(); // 构造新节点的条件node.right traversal(); // 右递归的条件传输node.left traversal(); // 左递归的条件传输return node;
}这里涉及到了逻辑切割数组可以查看一下我这篇博客的第三道题目 代码随想录刷题笔记 DAY 18 | 找树左下角的值 No.513 | 路经总和 No.112 | 从中序与后序遍历序列构造二叉树 No.106其实理解起来也很容易就是传入数组的起始和终止位置来约束来达到和分割数组相同的效果。 接下来就是依照题目去一点点解决这些问题了 构造节点的条件 这里才开始做和这道题目有关的事情首先题目交给的就已经是排序好的数组只需要保证左右子树平衡即可也就是考虑怎样分割数组的问题。 平衡就需要保证左子树和右子树的节点数量尽量相同那 分割点起始就是数组中间点。 将代码补充出来 int mid (startIndex endIndex) / 2;
Treenode node new TreeNode(nums[mid]);左右递归的条件传输 那分析到这里其实做有递归的条件也很容易写出来了就是从 startIndex 到 mid - 1 作为其左子树 mid 1 到 endIndex 作为其右子树。 将代码补充出来 node.left traversal(nums, startIndex, mid - 1);
node.right traversal(nums, mid 1, endIndex);递归的终点 当是实际的切割数组的时候终止条件其实很容易写出就是 nums null 的时候但是对于这种逻辑切割就要考虑一下了。 答案是 startIndex endIndex 而不是 startIndex endIndex因为在过程中如果出现表示的数组为空逻辑的起始和终止就会出现这种情况可以当作结论记忆。 将代码补充出来 if (startIndex endIndex) {return null;
}2.3 代码
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums, 0, (nums.length - 1));}public TreeNode traversal(int[] nums, int startIndex, int endIndex) {if (startIndex endIndex) {return null;}int mid (startIndex endIndex) / 2;TreeNode node new TreeNode(nums[mid]);node.left traversal(nums, startIndex, mid - 1);node.right traversal(nums, mid 1, endIndex);return node;}
}03. 把二叉搜索树转换为累加树No. 538
题目链接
代码随想录题解
3.1 题目
给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
**注意**本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1 输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] 示例 2 输入root [0,null,1] 输出[1,null,1] 示例 3 输入root [1,0,2] 输出[3,3,2] 示例 4 输入root [3,2,4,1] 输出[7,9,4,10] 提示
树中的节点数介于 0 和 104 之间。每个节点的值介于 -104 和 104 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。
3.2 笔记
题目中给出的是二叉搜索树来观察上面的 示例 1 累加树的特征为每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
二叉搜索树的最右边的节点是整个树中最大的节点也就是说大于等于它的节点就是它本身而再往上推到上图中的节点 7 作为次大的节点这个节点的值就是它本身加上比他大的值也就是 8按照这个规律很容易就能得出其他的节点的值节点 6 的值就是 6 7 8 而节点 5 的值就是 5 6 7 8。
所以这道题的思路就很明确了以 右、中、左 的顺序去遍历二叉树在这途中给节点加上路径中的节点和即可。
最后只需要解决如何按照 右、中、左 的顺序去遍历二叉树就可以了这其实就是一种另类的中序遍历
traversal(node.left);
System.out.println(node.val);
traversal(node.right);这样的遍历顺序是 左、中、右那修改一下
traversal(node.right);
System.out.println(node.val);
traversal(node.left);这样就能得到符合上面遍历顺序的值。
只要将输出语句改为对节点的操作就能达到倒序的操作树将搜索树看作升序数组。
定义一个全局变量为 0随着遍历逐步累加为 8 15 21 26 然后将其赋值给该节点即可。 globalNum node.val;
node.val globalNum;3.3 代码
class Solution {int globalNum 0;public TreeNode convertBST(TreeNode root) {traversal(root);return root;}public void traversal(TreeNode node) {if (node null) {return;}traversal(node.right);globalNum node.val;node.val globalNum;traversal(node.left);}
}
