代码随想录｜Day20｜二叉树09｜669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

思路：利用二叉搜索树的性质，对于每个节点，判断其是否在区间内：

• 如果节点值 < low，则此节点和其左子树都不在范围内
• 如果节点值 > high，则此节点和其右子树都不在范围内
• 如果 low < 节点值 < high，则保留此节点，但需要递归修建其左右子树

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return None# 如果节点小于low，返回右子树修剪的结果if root.val < low:return self.trimBST(root.right, low, high)# 如果节点大于high，返回左子树修剪的结果elif root.val > high:return self.trimBST(root.left, low, high)# 如果节点在区间内，递归修建左右子树else:root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

108.将有序数组转换为二叉搜索树

 思路：我们知道，按照中序遍历一个二叉搜索树将获得一个递增数组。因此我们可以将数组二分，中间元素所谓根节点，左边元素作为左子树，右边元素作为右子树，递归下去可以构成平衡二叉搜索树。

class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:def helper(left, right):if left > right:return Nonemid = (left + right) // 2root = TreeNode(nums[mid])root.left = helper(left, mid - 1)root.right = helper(mid + 1, right)return rootreturn helper(0, len(nums)-1)

538.把二叉搜索树转换为累加树

什么是累加树？

指在二叉搜索树（BST）的基础上进行转换得到的一种特殊形式的树。在累加树中，每个节点的值被替换为原始二叉搜索树中所有大于该节点值的节点值之和加上该节点自身的值。

思路：我们从最大值开始累加，因此遍历顺序是元素从大到小。我们可以使用反向中序遍历来实现：右中左。

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.sum = 0def traverse(node):if not node:return# 反向中序遍历：右 -> 根 -> 左traverse(node.right)self.sum += node.valnode.val = self.sumtraverse(node.left)traverse(root)return root