目录669. 修剪二叉搜索树题目描述解题思路108. 将有序数组转换为二叉搜索树题目描述解题思路538. 把二叉搜索树转换为累加树题目描述解题思路小结669. 修剪二叉搜索树题目描述给你二叉搜索树的根节点root同时给定最小边界low和最大边界high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。解题思路看到特定区间就该庆幸了此题不需要像之前那个450. 删除二叉搜索树中的节点考虑五种情况为什么呢因为我们要确保二叉树在特定区间范围对于一个节点只有三种情况在区间内比区间数小比区间数大为什么只需要考虑三种情况呢因为对于我们二叉搜索树而言如果一个节点区间那么它的左孩子一定小于区间为什么呢由二叉搜索树的特性决定节点的左子树的所有值都严格小于节点节点的右子树的所有值都严格大于节点那么节点区间就同理了那么此时删除一个节点就根本不需要改变树的结构那么就分三种情况节点区间去掉左子树递归遍历修剪好的右子树怎么去实现修剪的逻辑呢节点区间去掉右子树递归遍历保留修剪好的右子树节点在区间内递归遍历左子树右子树将修建好的树都返回那么如何实现修剪的逻辑呢其实答案就在root.vallow和root.valhigh中从两个方面思考一下当此时不符合要求的是叶子节点那么它会返回None对于上一层的节点来说不管是左孩子还是右孩子留下的都是符合要求的如若此时不符合要求的是根节点按照上面的逻辑返回他相应的子树此时就实现了删掉该节点的逻辑了对于节点来说无非就以上两种情况如此反复就成功修剪class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) - Optional[TreeNode]: if not root:return None if root.val low:return self.trimBST(root.right,low,high) elif root.val high:return self.trimBST(root.left,low,high) root.left self.trimBST(root.left,low,high) root.right self.trimBST(root.right,low,high) return root108. 将有序数组转换为二叉搜索树题目描述给你一个整数数组nums其中元素已经按升序排列请你将其转换为一棵 平衡 二叉搜索树。解题思路创造一棵树首先要考虑根节点节点的左孩子右孩子在有序数组中数组最中间的节点就是根节点左区间为左孩子右区间为右孩子class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums:return None seg_num len(nums)//2 root TreeNode(nums[seg_num]) root.left self.sortedArrayToBST(nums[:seg_num]) root.right self.sortedArrayToBST(nums[seg_num1:]) return root538. 把二叉搜索树转换为累加树题目描述给出二叉搜索树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点node的新值等于原树中大于或等于node.val的值之和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。解题思路分析来看本题其实本质就是将数组从末尾开始计算累加和那么二叉树该如何实现这种倒序计算呢已知二叉搜索树按照中序遍历左中右可以输出升序数组那么将其倒过来右中左即可实现降序数组此时就可以按照计算累加和的办法---双指针来完成此题我在完成该题过程中由于不熟练将倒序遍历写成中左右导致例子中的6处的值变为26本该是21我想是由于加上了5即遍历顺序出现问题关于travesal我的重大问题def travesal(self,cur): if not cur:return 0 right self.travesal(cur.right) cur.val cur.val right left self.travesal(cur.left) return cur.val做完再回看第一次的代码使用了返回值来进行累加但这个逻辑其实是错的因为此时的节点 节点自身右子树的返回值但是题目其实是节点 节点自身比它大的和的累加和举个栗子4 | | 3 8 | | 5 10对于8和10他们的最后结果是18和10没有问题但是此时的5右子树返回值0节点自身5但其实是23所以对于此题返回值解法是完全错误的因此此题就可以使用双指针或者设置一个全局变量total来存储之前的累加和两者本身是一致的可以设一个树节点也可以设int类型的全局变量class Solution: def __init__(self): self.pre None def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: self.travesal(root) return root def travesal(self,cur): if not cur:return self.travesal(cur.right) #cur指向根节点时pre为空 if self.pre: cur.val self.pre.val cur.val #cur操作完成后进入下一个递归此时保留pre值 self.pre cur self.travesal(cur.left)小结今天的题总归来讲没有那么难二叉树的解题实质还是要先思考三部曲修剪二叉搜索树时需按区间递归判断并直接返回对应子树有序数组转平衡二叉搜索树采用分治法每次取中间元素建根左右递归构建以保证平衡将二叉搜索树转为累加树需使用反中序遍历右 - 根 - 左配合全局累加变量实现从大到小依次累加更新节点值整体递归框架思路正确主要问题集中在变量使用、返回值逻辑和累加方式等细节上稍加修正即可实现正确解法。