669. 修剪二叉搜索树
目标：
给一棵 BST 和区间[low, high]，删除所有值不在区间内的节点，并返回修剪后的新 root。
核心思路（先记住这 3 句）
BST + 区间 = 剪整棵子树
root.val < low→ 整个左子树都不要root.val > high→ 整个右子树都不要- 否则 → 保留当前节点，递归修剪左右
为什么可以“整棵剪”？（BST 性质）
- 若
root.val < low
👉 左子树所有值 <root.val < low→ 全不合法- 若
root.val > high
👉 右子树所有值 >root.val > high→ 全不合法
定义： trimBST(node)返回「以 node 为根，修剪完成后的子树的新根」 过程：-若 node 为空：returnNone（这棵子树不存在）-若 node.val<low： 当前节点不合法returntrimBST(node.right)-若 node.val>high： 当前节点不合法returntrimBST(node.left)-否则： 当前节点合法 左子树的新根=trimBST(node.left)右子树的新根=trimBST(node.right)将新左右子树接回 nodereturnnode代码
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:deftrimBST(self,root:Optional[TreeNode],low:int,high:int)->Optional[TreeNode]:# 【base case】# 走到空节点，说明这条路径已经没有节点了# 返回 None 表示：这棵子树修剪后不存在ifnotroot:returnNone# 【情况 1：当前节点太小】# root.val < low：# - 当前节点不合法，不能出现在最终结果中# - 根据 BST 性质，左子树一定也都 < low，可以整体丢掉# - 这棵子树新的 root 只能来自右子树# 所以：直接返回「右子树修剪后的新根」ifroot.val<low:returnself.trimBST(root.right,low,high)# 【情况 2：当前节点太大】# root.val > high：# - 当前节点不合法# - 右子树一定也都 > high，可以整体丢掉# - 新的 root 只能来自左子树ifroot.val>high:returnself.trimBST(root.left,low,high)# 【情况 3：当前节点合法】# root.val 在 [low, high] 内# - 当前节点可以保留# - 但左右子树是否保留，要等递归返回结果# 这里不会立刻 return，而是“接住”下一层的返回值root.left=self.trimBST(root.left,low,high)root.right=self.trimBST(root.right,low,high)# 左右子树都已经修剪完成# 当前 root 仍然合法，作为这一层子树的新根返回returnroot| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(h) | 只沿 BST 高度剪枝 |
| 空间复杂度 | O(h) | 递归调用栈 |
108.将有序数组转换为二叉搜索树
目标：
给一个升序数组nums，把它转换成一棵高度平衡的 BST，并返回root。
核心思路
每一次递归都做同一件事：
👉 选当前区间的中点作为 root（保证左右子树高度接近）
👉 左半边数组 → 左子树
👉 右半边数组 → 右子树
👉 return 当前构造好的 root
代码
情况一：区间递归（helper(l, r)）
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsortedArrayToBST(self,nums:List[int])->Optional[TreeNode]:# helper(l, r) 的语义：# 👉 用 nums[l..r]（闭区间）构造一棵 BST，# 👉 并返回这棵子树构造完成后的「根节点」defhelper(l,r):# 【base case】# 当区间为空（l > r），说明这段数组构不成子树# 返回 None，表示“这棵子树不存在”ifl>r:returnNone# 1️⃣ 选择当前区间的中点作为根节点# 因为数组有序，选中点可以保证左右子树高度接近mid=(l+r)//2node=TreeNode(nums[mid])# 2️⃣ 构造左子树# 左子树使用区间 [l, mid-1]# helper 返回的是：左子树构造完成后的新根node.left=helper(l,mid-1)# 3️⃣ 构造右子树# 右子树使用区间 [mid+1, r]# 注意：这里必须是 r，而不是 r+1# 因为我们始终使用的是闭区间 [l, r]node.right=helper(mid+1,r)# 4️⃣ 左右子树都已经构造完成# 当前 node 就是这段区间对应子树的新根# return 给上一层递归使用returnnode# 从整个数组区间 [0, n-1] 开始构造returnhelper(0,len(nums)-1)| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个数组元素只被用来创建一个节点 |
| 空间复杂度 | O(log n) | 递归深度等于平衡 BST 的高度 |
情况二：切片递归（nums[:mid]）
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defsortedArrayToBST(self,nums:List[int])->Optional[TreeNode]:# 递归函数的“语义”：# sortedArrayToBST(nums) 返回：# 👉 用当前 nums（这个子数组）构造出的 BST 的根节点# 【base case】# 当数组为空，说明这段数据构不成子树# 返回 None，表示“这棵子树不存在”ifnotnums:returnNone# 1️⃣ 选择当前数组的中点作为根节点# 因为 nums 是有序的，选中点可以保证左右子树高度接近mid=len(nums)//2root=TreeNode(nums[mid])# 2️⃣ 用中点左边的子数组递归构造左子树# 递归返回的是：左子树构造完成后的新 rootroot.left=self.sortedArrayToBST(nums[:mid])# 3️⃣ 用中点右边的子数组递归构造右子树# 返回的是：右子树构造完成后的新 rootroot.right=self.sortedArrayToBST(nums[mid+1:])# 4️⃣ 左右子树都已经构造完成# 当前 root 作为“这棵子树的新根”返回给上一层returnroot| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 每一层递归都会拷贝数组切片 |
| 空间复杂度 | O(n) | 所有递归层产生的切片数组占用内存 |
538.把二叉搜索树转换为累加树
目标：
给一棵 BST，把每个节点的值改成：
原值 + 所有比它大的节点值之和
返回修改后的 root。
核心思路
BST 的中序遍历是升序
👉 想从「大到小」累加
👉 就用反向中序遍历：右 → 根 → 左
在遍历过程中，维护一个running sum（累计和）。
BST 性质
左子树 < 根 < 右子树
- 普通中序：
左 → 根 → 右（小 → 大）- 反向中序：
右 → 根 → 左（大 → 小）👉 我们要先看到“更大的值”，才能加给当前节点。
total（running sum）的含义：
`total`表示在反向中序遍历中， 已经访问过的所有节点值之和=所有比当前节点大的节点之和- 一开始
total = 0 - 每访问一个节点：
- 先把当前节点值加到
total - 再用
total更新当前节点的值
- 先把当前节点值加到
代码
classSolution:defconvertBST(self,root):# total 的含义（非常重要）：# 👉 在反向中序遍历过程中，# 👉 已经访问过的所有节点值之和# 👉 也就是“当前节点右边（更大）的所有节点之和”total=0defreverse_inorder(node):nonlocaltotalifnotnode:return# 1️⃣ 先访问右子树# 因为 BST 中：右子树的值都比当前节点大# 所以先处理右边，才能先累加“更大的值”reverse_inorder(node.right)# 2️⃣ 处理当前节点# 走到这里时：# total 已经等于：# 所有「比 node.val 大的节点值之和」## 现在我们把当前节点也加进去total+=node.val# 更新当前节点的值：# 新值 = 原值 + 所有比它大的值node.val=total# 3️⃣ 再访问左子树# 左子树里的值都比当前节点小# 但它们要加的是：# 包含当前节点在内的 totalreverse_inorder(node.left)reverse_inorder(root)returnroot| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个节点在反向中序遍历中访问一次 |
| 空间复杂度 | O(h) | 递归调用栈深度等于树高 |
