1. 二叉搜索树基础概念回顾二叉搜索树Binary Search Tree, BST是一种特殊的二叉树数据结构它具有以下关键性质对于树中的每个节点其左子树所有节点的值都小于该节点的值右子树所有节点的值都大于该节点的值左右子树也必须是二叉搜索树这种结构特性使得BST在查找、插入和删除操作时都能保持O(log n)的平均时间复杂度。让我们通过一个简单的例子来理解class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 一个合法的BST示例 # 4 # / \ # 2 6 # / \ / \ # 1 3 5 7BST的这种有序特性使得它在许多算法问题中都有重要应用包括我们今天要讨论的三个经典问题。注意BST的性质是解决所有相关问题的基础必须确保在任何操作后都保持这个性质不被破坏。2. 修剪二叉搜索树LeetCode 6692.1 问题定义与理解给定一个二叉搜索树的根节点和两个边界值low和high我们需要修剪树使得所有节点的值都在[low, high]范围内。修剪后的树仍然应该保持BST的性质。例如 输入root [3,0,4,null,2,null,null,1], low 1, high 3 输出[3,2,null,1]2.2 递归解法详解递归是解决树问题的自然思路。对于当前节点我们需要考虑三种情况当前节点值 low说明当前节点及其左子树都应该被修剪掉只需处理右子树当前节点值 high说明当前节点及其右子树都应该被修剪掉只需处理左子树当前节点值在范围内保留该节点递归处理左右子树def trimBST(root, low, high): if not root: return None if root.val low: 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 root2.3 迭代解法实现虽然递归简洁但理解迭代解法有助于深入掌握BST的操作逻辑def trimBST(root, low, high): # 首先找到新的根节点 while root and (root.val low or root.val high): if root.val low: root root.right else: root root.left # 修剪左子树 node root while node: while node.left and node.left.val low: node.left node.left.right node node.left # 修剪右子树 node root while node: while node.right and node.right.val high: node.right node.right.left node node.right return root2.4 复杂度分析与边界情况时间复杂度O(n)每个节点最多被访问一次 空间复杂度递归解法O(h)h为树高迭代解法O(1)边界情况处理空树的处理所有节点都小于low或大于high的情况low和high相等的情况3. 将有序数组转换为二叉搜索树LeetCode 1083.1 问题描述与转化思路给定一个升序排列的整数数组将其转换为高度平衡的二叉搜索树。高度平衡意味着每个节点的左右子树高度差不超过1。关键观察数组已排序相当于BST的中序遍历结果要保证平衡应该选择中间元素作为根节点3.2 递归构建平衡BSTdef sortedArrayToBST(nums): def helper(left, right): if left right: return None mid (left right) // 2 root TreeNode(nums[mid]) root.left helper(left, mid - 1) root.right helper(mid 1, right) return root return helper(0, len(nums) - 1)3.3 选择中间节点的变体有时候面试官会问为什么选择中间偏左或偏右的节点。这其实不影响平衡性# 选择中间偏右的节点 mid (left right 1) // 2 # 或者随机选择 import random mid random.choice([(left right) // 2, (left right 1) // 2])3.4 迭代解法与复杂度分析虽然递归更直观但迭代解法可以避免栈溢出风险def sortedArrayToBST(nums): if not nums: return None root TreeNode(0) stack [(root, 0, len(nums) - 1)] while stack: node, left, right stack.pop() mid (left right) // 2 node.val nums[mid] if left mid - 1: node.left TreeNode(0) stack.append((node.left, left, mid - 1)) if mid 1 right: node.right TreeNode(0) stack.append((node.right, mid 1, right)) return root时间复杂度O(n)每个元素被处理一次 空间复杂度O(log n)用于递归栈或迭代栈4. 把二叉搜索树转换为累加树LeetCode 5384.1 问题理解与转换规则给定一个BST将其转换为累加树Greater Tree使得每个节点的值变成原树中大于或等于该节点值的所有节点值之和。例如 输入[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]4.2 反序中序遍历解法关键思路是利用BST的性质通过反序中序遍历右-根-左来累加节点值def convertBST(root): total 0 def helper(node): nonlocal total if not node: return helper(node.right) total node.val node.val total helper(node.left) helper(root) return root4.3 迭代实现与Morris遍历迭代版本使用显式栈def convertBST(root): total 0 stack [] node root while stack or node: while node: stack.append(node) node node.right node stack.pop() total node.val node.val total node node.left return root更高效的Morris遍历版本def convertBST(root): total 0 node root while node: if not node.right: total node.val node.val total node node.left else: succ node.right while succ.left and succ.left ! node: succ succ.left if not succ.left: succ.left node node node.right else: succ.left None total node.val node.val total node node.left return root4.4 复杂度分析与应用场景时间复杂度递归和迭代O(n)Morris遍历O(n)时间O(1)空间应用场景统计类问题如计算超过某个阈值的所有数据总和金融领域中的累计收益计算游戏中的积分排名系统5. 三种操作的关联与对比5.1 共同依赖的BST性质这三种操作都深度依赖BST的有序性质修剪BST利用节点值的大小关系决定修剪方向有序数组转BST利用中序遍历的有序性累加树利用反序中序遍历的累加特性5.2 遍历方式的差异修剪BST前序遍历先处理当前节点再递归子树有序数组转BST类似于二分查找的访问顺序累加树反序中序遍历从大到小访问节点5.3 实际应用中的选择数据过滤修剪BST数据存储优化有序数组转BST如内存数据库索引构建统计分析累加树模式6. 常见错误与调试技巧6.1 修剪BST时的易错点忘记处理修剪后的子树可能也需要修剪的情况错误示例只检查当前节点就返回子树正确做法递归处理子树边界条件处理不当测试案例lowhigh节点值所有节点都小于low等6.2 构建平衡BST的陷阱中间节点计算错误导致不平衡确保使用(left right) // 2而不是len(nums) // 2数组切片导致的高空间复杂度避免nums[mid1:]这样的切片操作改为传递索引6.3 累加树的调试技巧使用小规模树手动验证先构建3-5个节点的BST手动计算预期结果打印中序遍历序列转换前后都打印中序序列验证顺序是否正确def inorder(root): return inorder(root.left) [root.val] inorder(root.right) if root else []7. 性能优化与进阶思考7.1 修剪BST的优化方向并行修剪对于多核系统可以并行处理左右子树迭代剪枝对于特别大的树使用迭代避免栈溢出7.2 平衡BST构建的变体处理频繁更新的有序数据流使用AVL树或红黑树等自平衡BST增量式更新而非全量重建考虑节点大小的平衡重量平衡树不仅考虑高度还考虑各子树的大小关系7.3 累加树的高级应用支持动态更新的累加树当树节点值变化时如何高效维护累加值使用线段树或树状数组等辅助数据结构区间累加查询扩展问题查询某个区间范围内的累加值解决方案为每个节点存储子树的和8. 实战练习建议为了真正掌握这三种BST操作建议按以下顺序练习基础实现先独立完成每种操作的递归版本边界测试设计各种极端测试用例空树、单节点、全左/右偏树等迭代实现将递归解法转换为迭代版本综合应用尝试解决需要组合这些操作的问题例如先修剪BST再转换为累加树将有序数组转为BST后进行修剪这里提供一个综合练习的示例代码def process_tree(nums, low, high): # 将有序数组转为BST bst sortedArrayToBST(nums) # 修剪BST trimmed trimBST(bst, low, high) # 转换为累加树 result convertBST(trimmed) return result通过这样的综合练习可以深入理解这些操作之间的相互关系和在复杂问题中的应用方式。