二叉搜索树操作精解：修剪、构建与累加转换

1. 二叉搜索树基础与LeetCode刷题策略二叉搜索树BST作为数据结构中的常青树在算法面试中出现的频率居高不下。今天我们就来深度剖析LeetCode中三道典型的BST题目669修剪、108构建和538转换。这三道题看似独立实则暗含BST操作的完整知识链条。对于BST的常规操作时间复杂度通常为O(h)其中h是树的高度。在平衡情况下能达到O(log n)这也是为什么面试官如此钟爱考察这类问题。下面这张表对比了三道题的核心考点题目编号操作类型时间复杂度空间复杂度关键技巧669修剪O(n)O(n)递归终止条件判断108构建O(n)O(log n)中点分割策略538累加转换O(n)O(n)反序中序遍历提示在BST问题中递归解法往往比迭代更简洁但要注意栈空间消耗。对于特别深的树考虑使用Morris遍历来优化空间。1.1 题目背景解析669题要求我们修剪BST只保留值在[L,R]范围内的节点。这看似简单但实际处理时需要特别注意父子节点关系的调整。比如当根节点值小于L时不能简单删除根节点还要考虑其右子树中可能存在的有效节点。108题则是BST的逆向工程——给定有序数组构建高度平衡的BST。这里高度平衡的定义是左右子树高度差不超过1。解题关键在于发现数组中点与树根的关系。538题引入了累加树的概念即将每个节点的值替换为所有大于等于它的节点值之和。这种反向累加的特性提示我们需要从大到小遍历节点这正是BST反序中序遍历的用武之地。2. 669. 修剪二叉搜索树深度解析2.1 递归解法实现细节修剪BST的核心在于正确处理三种情况当前节点值在[L,R]范围内保留该节点递归处理其左右子树当前节点值小于L该节点及其左子树都应被修剪仅需处理右子树当前节点值大于R该节点及其右子树都应被修剪仅需处理左子树def trimBST(root, L, R): if not root: return None if root.val L: return trimBST(root.right, L, R) if root.val R: return trimBST(root.left, L, R) root.left trimBST(root.left, L, R) root.right trimBST(root.right, L, R) return root这个实现看似简单但有几个精妙之处当root.val L时直接返回右子树的修剪结果跳过了对左子树的处理递归调用是后序的先处理子树再决定当前节点的连接始终返回符合条件的子树根节点保持了树的连接性2.2 边界条件与测试用例在实际编码时特别需要注意以下边界情况空树输入L等于R且等于某个节点值L或R等于树中的最小/最大值整个树都在范围之外这里给出一个典型的测试用例输入: 3 / \ 0 4 \ 2 / 1 L 1, R 3 输出: 3 / 2 / 1注意当处理root.val L的情况时不能直接返回None因为右子树中可能存在有效节点。这是新手常犯的错误。3. 108. 将有序数组转换为二叉搜索树3.1 分治算法的精妙应用这道题要求构建高度平衡的BST分治策略是最佳选择。每次选择数组中间元素作为根节点左侧子数组构建左子树右侧构建右子树。这种策略天然保证了树的平衡性。def 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)关键点分析中点选择使用(left right) // 2实现整数除法对于偶数长度数组选择靠左的中位数递归终止条件当left right时表示当前子数组为空空间复杂度O(log n)的栈空间因为每次都将问题规模减半3.2 多种平衡构建方式探讨虽然题目只要求高度平衡但实际上存在多种构建方式。例如对于数组[1,2,3,4,5]以下是两种合法的BST3 4 / \ / \ 1 4 2 5 \ / \ / \ / 2 5 6 1 3 6在面试中可以主动提出这种多样性展示对问题的深入理解。同时要说明选择中间元素作为根节点的优势保证左右子树节点数差值不超过1生成的树高度最小约为log2(n)实现简单代码直观4. 538. 把二叉搜索树转换为累加树4.1 反序中序遍历的魔力累加树的核心思想是反向累加即从最大的节点开始遍历维护一个累加和。这正好对应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 root算法流程解析定义total变量记录累加和先递归处理右子树较大的值更新当前节点值并累加到total最后处理左子树较小的值时间复杂度分析每个节点被访问一次O(n)时间复杂度空间复杂度取决于树的高度最坏情况O(n)4.2 迭代实现与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遍历优化空间复杂度到O(1)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 root注意Morris遍历虽然节省空间但会临时修改树的结构建立临时链接这在生产环境中可能需要谨慎考虑。5. 三题联解与举一反三5.1 解题模式总结通过这三道题我们可以总结出BST问题的通用解法模式遍历方向选择常规中序遍历得到升序序列反序中序遍历得到降序序列如538题前序/后序遍历用于构建/修剪操作递归与迭代转换递归代码简洁适合面试快速实现迭代节省栈空间适合深度大的树Morris遍历是空间最优解边界条件处理空树处理单节点处理极值处理如669题中整个子树超出范围5.2 相似题目扩展根据这三道题的解题思路可以扩展到以下LeetCode题目删除BST中的节点类似669的修剪逻辑有序链表转换BST108题的链表版本从BST到更大和树538题的变种BST中第K小的元素中序遍历应用BST中的中序后继遍历顺序理解在解决BST问题时我习惯先在白板上画出几个具体的例子手动模拟操作过程。这种方法往往能帮助我发现递归中的边界条件问题。比如在修剪BST时最初我忽略了右子树可能存在的有效节点导致提交失败。后来通过手动模拟一个右子树部分节点在范围内的案例才发现了这个问题。