1. 二叉搜索树基础回顾与问题拆解在开始这三道题目之前我们需要先明确几个核心概念。二叉搜索树BST是一种特殊的二叉树结构它满足以下性质左子树所有节点的值小于根节点的值右子树所有节点的值大于根节点的值左右子树也分别是二叉搜索树这个看似简单的定义在实际应用中却蕴含着强大的威力。BST的平均时间复杂度为O(log n)这使得它在数据查找、排序等领域有着广泛应用。但BST的性能高度依赖于树的平衡性这也是为什么我们需要掌握平衡BST的构建方法。今天要解决的三个问题分别代表了BST操作的三个典型场景修剪BST669题在保持BST性质的前提下对树结构进行修改有序数组转平衡BST108题从线性结构构建最优化的BSTBST转累加树538题对BST节点值进行全局性修改2. 669. 修剪二叉搜索树 - 选择性保留子树的艺术2.1 问题理解与边界分析题目要求我们修剪BST使得所有节点的值都在给定范围[low, high]内。这看似简单但实际操作中需要考虑多种边界情况当前节点值 low该节点及其左子树都应被修剪当前节点值 high该节点及其右子树都应被修剪low ≤ 当前节点值 ≤ high保留该节点递归处理左右子树关键难点在于当节点值超出范围时不能简单地返回null因为其子树中可能存在符合条件的节点。例如输入root [3,0,4,null,2,null,null,1], low 1, high 3 输出[3,2,null,1]在这个例子中根节点3符合要求其左子节点0超出下限但0的右子树2符合要求。2.2 递归解法实现细节递归是解决树问题的自然选择。下面是Java实现的核心逻辑public TreeNode trimBST(TreeNode root, int low, int high) { if (root null) return null; // 当前节点值小于下限保留右子树可能符合 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 root; }时间复杂度分析每个节点最多被访问一次因此时间复杂度为O(n)空间复杂度取决于递归深度最坏情况下为O(n)。2.3 迭代法实现与优化虽然递归解法简洁但在实际工程中我们可能需要考虑用迭代法避免栈溢出风险。迭代法的关键在于如何正确地重新连接节点public TreeNode trimBST(TreeNode root, int low, int high) { // 步骤1找到新的根节点第一个符合范围的节点 while (root ! null (root.val low || root.val high)) { root root.val low ? root.right : root.left; } if (root null) return null; // 步骤2修剪左子树 TreeNode node root; while (node.left ! null) { if (node.left.val low) { node.left node.left.right; } else { node node.left; } } // 步骤3修剪右子树 node root; while (node.right ! null) { if (node.right.val high) { node.right node.right.left; } else { node node.right; } } return root; }3. 108. 将有序数组转换为平衡二叉搜索树3.1 平衡BST的重要性与构建原则平衡BST是指左右子树高度差不超过1的BST。平衡性保证了树的查询效率维持在O(log n)级别。从有序数组构建平衡BST的关键在于选择中间元素作为根节点保证左右子树节点数平衡递归处理左右子数组当子数组为空时返回null这种构建方式类似于二分查找因此生成的BST自然就是平衡的。3.2 递归实现与变种标准递归实现如下public TreeNode sortedArrayToBST(int[] nums) { return buildBST(nums, 0, nums.length - 1); } private TreeNode buildBST(int[] nums, int left, int right) { if (left right) return null; int mid left (right - left) / 2; TreeNode root new TreeNode(nums[mid]); root.left buildBST(nums, left, mid - 1); root.right buildBST(nums, mid 1, right); return root; }有趣的是选择中间节点时我们有两种方式mid left (right - left) / 2偏向左侧mid left (right - left 1) / 2偏向右侧这两种选择都会产生合法的平衡BST只是具体结构略有不同。这在某些特定场景下可能有微妙的性能差异。3.3 迭代解法与性能考量虽然递归解法简洁但我们可以用队列模拟递归过程实现迭代解法public TreeNode sortedArrayToBST(int[] nums) { if (nums null || nums.length 0) return null; QueueObject[] queue new LinkedList(); TreeNode root new TreeNode(0); // 临时值 queue.offer(new Object[]{0, nums.length - 1, root}); while (!queue.isEmpty()) { Object[] curr queue.poll(); int left (int)curr[0], right (int)curr[1]; TreeNode node (TreeNode)curr[2]; int mid left (right - left) / 2; node.val nums[mid]; if (left mid - 1) { node.left new TreeNode(0); queue.offer(new Object[]{left, mid - 1, node.left}); } if (mid 1 right) { node.right new TreeNode(0); queue.offer(new Object[]{mid 1, right, node.right}); } } return root; }这种实现虽然代码量增加但在处理极大数组时可以避免递归深度过大的问题。4. 538. 把二叉搜索树转换为累加树4.1 问题理解与转换逻辑累加树的定义是每个节点的值等于原树中大于或等于该节点值的所有节点值之和。对于BST来说节点的排序关系非常明确因此可以采用逆中序遍历右-根-左的方式累加节点值。例如输入[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 递归实现与累加技巧标准的递归实现需要维护一个全局累加变量private int sum 0; public TreeNode convertBST(TreeNode root) { if (root null) return null; convertBST(root.right); // 先处理右子树 sum root.val; // 累加当前节点值 root.val sum; // 更新当前节点值 convertBST(root.left); // 最后处理左子树 return root; }这种方法简洁明了但使用了成员变量在多次调用时需要注意重置sum。我们可以通过参数传递来避免这个问题public TreeNode convertBST(TreeNode root) { traverse(root, new int[]{0}); return root; } private void traverse(TreeNode root, int[] sum) { if (root null) return; traverse(root.right, sum); sum[0] root.val; root.val sum[0]; traverse(root.left, sum); }4.3 迭代实现与Morris遍历对于大型树或需要优化空间复杂度的情况我们可以使用迭代法public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode node root; StackTreeNode stack new Stack(); while (!stack.isEmpty() || node ! null) { while (node ! null) { stack.push(node); node node.right; } node stack.pop(); sum node.val; node.val sum; node node.left; } return root; }更进一步我们可以使用Morris遍历实现O(1)空间复杂度的解法public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode node root; while (node ! null) { if (node.right null) { sum node.val; node.val sum; node node.left; } else { TreeNode succ getSuccessor(node); if (succ.left null) { succ.left node; node node.right; } else { succ.left null; sum node.val; node.val sum; node node.left; } } } return root; } private TreeNode getSuccessor(TreeNode node) { TreeNode succ node.right; while (succ.left ! null succ.left ! node) { succ succ.left; } return succ; }5. 三道题目的共通技巧与进阶思考5.1 递归与迭代的选择策略在处理树问题时我们通常优先考虑递归解法因为代码简洁更符合树结构的自然表达更容易验证正确性大多数情况下时间复杂度相同但在实际工程中迭代法可能更适合避免递归深度过大导致的栈溢出某些语言对递归优化不足需要更精确控制遍历过程时5.2 BST遍历的顺序魔法这三道题目展示了BST遍历顺序的灵活性修剪BST前序遍历先处理当前节点构建平衡BST类似于二分的中序遍历累加树逆中序遍历右-根-左理解这些遍历顺序的差异是解决BST问题的关键。5.3 实际应用场景举例这些算法在实际中有广泛应用修剪BST数据库索引的范围查询优化平衡BST内存数据库的索引结构实现累加树统计分析和累计分布计算例如在金融系统中累加树可以高效计算账户余额的累计分布在游戏开发中平衡BST可用于快速查找排行榜数据。 二叉搜索树操作实战：修剪、构建与累加
1. 二叉搜索树基础回顾与问题拆解在开始这三道题目之前我们需要先明确几个核心概念。二叉搜索树BST是一种特殊的二叉树结构它满足以下性质左子树所有节点的值小于根节点的值右子树所有节点的值大于根节点的值左右子树也分别是二叉搜索树这个看似简单的定义在实际应用中却蕴含着强大的威力。BST的平均时间复杂度为O(log n)这使得它在数据查找、排序等领域有着广泛应用。但BST的性能高度依赖于树的平衡性这也是为什么我们需要掌握平衡BST的构建方法。今天要解决的三个问题分别代表了BST操作的三个典型场景修剪BST669题在保持BST性质的前提下对树结构进行修改有序数组转平衡BST108题从线性结构构建最优化的BSTBST转累加树538题对BST节点值进行全局性修改2. 669. 修剪二叉搜索树 - 选择性保留子树的艺术2.1 问题理解与边界分析题目要求我们修剪BST使得所有节点的值都在给定范围[low, high]内。这看似简单但实际操作中需要考虑多种边界情况当前节点值 low该节点及其左子树都应被修剪当前节点值 high该节点及其右子树都应被修剪low ≤ 当前节点值 ≤ high保留该节点递归处理左右子树关键难点在于当节点值超出范围时不能简单地返回null因为其子树中可能存在符合条件的节点。例如输入root [3,0,4,null,2,null,null,1], low 1, high 3 输出[3,2,null,1]在这个例子中根节点3符合要求其左子节点0超出下限但0的右子树2符合要求。2.2 递归解法实现细节递归是解决树问题的自然选择。下面是Java实现的核心逻辑public TreeNode trimBST(TreeNode root, int low, int high) { if (root null) return null; // 当前节点值小于下限保留右子树可能符合 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 root; }时间复杂度分析每个节点最多被访问一次因此时间复杂度为O(n)空间复杂度取决于递归深度最坏情况下为O(n)。2.3 迭代法实现与优化虽然递归解法简洁但在实际工程中我们可能需要考虑用迭代法避免栈溢出风险。迭代法的关键在于如何正确地重新连接节点public TreeNode trimBST(TreeNode root, int low, int high) { // 步骤1找到新的根节点第一个符合范围的节点 while (root ! null (root.val low || root.val high)) { root root.val low ? root.right : root.left; } if (root null) return null; // 步骤2修剪左子树 TreeNode node root; while (node.left ! null) { if (node.left.val low) { node.left node.left.right; } else { node node.left; } } // 步骤3修剪右子树 node root; while (node.right ! null) { if (node.right.val high) { node.right node.right.left; } else { node node.right; } } return root; }3. 108. 将有序数组转换为平衡二叉搜索树3.1 平衡BST的重要性与构建原则平衡BST是指左右子树高度差不超过1的BST。平衡性保证了树的查询效率维持在O(log n)级别。从有序数组构建平衡BST的关键在于选择中间元素作为根节点保证左右子树节点数平衡递归处理左右子数组当子数组为空时返回null这种构建方式类似于二分查找因此生成的BST自然就是平衡的。3.2 递归实现与变种标准递归实现如下public TreeNode sortedArrayToBST(int[] nums) { return buildBST(nums, 0, nums.length - 1); } private TreeNode buildBST(int[] nums, int left, int right) { if (left right) return null; int mid left (right - left) / 2; TreeNode root new TreeNode(nums[mid]); root.left buildBST(nums, left, mid - 1); root.right buildBST(nums, mid 1, right); return root; }有趣的是选择中间节点时我们有两种方式mid left (right - left) / 2偏向左侧mid left (right - left 1) / 2偏向右侧这两种选择都会产生合法的平衡BST只是具体结构略有不同。这在某些特定场景下可能有微妙的性能差异。3.3 迭代解法与性能考量虽然递归解法简洁但我们可以用队列模拟递归过程实现迭代解法public TreeNode sortedArrayToBST(int[] nums) { if (nums null || nums.length 0) return null; QueueObject[] queue new LinkedList(); TreeNode root new TreeNode(0); // 临时值 queue.offer(new Object[]{0, nums.length - 1, root}); while (!queue.isEmpty()) { Object[] curr queue.poll(); int left (int)curr[0], right (int)curr[1]; TreeNode node (TreeNode)curr[2]; int mid left (right - left) / 2; node.val nums[mid]; if (left mid - 1) { node.left new TreeNode(0); queue.offer(new Object[]{left, mid - 1, node.left}); } if (mid 1 right) { node.right new TreeNode(0); queue.offer(new Object[]{mid 1, right, node.right}); } } return root; }这种实现虽然代码量增加但在处理极大数组时可以避免递归深度过大的问题。4. 538. 把二叉搜索树转换为累加树4.1 问题理解与转换逻辑累加树的定义是每个节点的值等于原树中大于或等于该节点值的所有节点值之和。对于BST来说节点的排序关系非常明确因此可以采用逆中序遍历右-根-左的方式累加节点值。例如输入[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 递归实现与累加技巧标准的递归实现需要维护一个全局累加变量private int sum 0; public TreeNode convertBST(TreeNode root) { if (root null) return null; convertBST(root.right); // 先处理右子树 sum root.val; // 累加当前节点值 root.val sum; // 更新当前节点值 convertBST(root.left); // 最后处理左子树 return root; }这种方法简洁明了但使用了成员变量在多次调用时需要注意重置sum。我们可以通过参数传递来避免这个问题public TreeNode convertBST(TreeNode root) { traverse(root, new int[]{0}); return root; } private void traverse(TreeNode root, int[] sum) { if (root null) return; traverse(root.right, sum); sum[0] root.val; root.val sum[0]; traverse(root.left, sum); }4.3 迭代实现与Morris遍历对于大型树或需要优化空间复杂度的情况我们可以使用迭代法public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode node root; StackTreeNode stack new Stack(); while (!stack.isEmpty() || node ! null) { while (node ! null) { stack.push(node); node node.right; } node stack.pop(); sum node.val; node.val sum; node node.left; } return root; }更进一步我们可以使用Morris遍历实现O(1)空间复杂度的解法public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode node root; while (node ! null) { if (node.right null) { sum node.val; node.val sum; node node.left; } else { TreeNode succ getSuccessor(node); if (succ.left null) { succ.left node; node node.right; } else { succ.left null; sum node.val; node.val sum; node node.left; } } } return root; } private TreeNode getSuccessor(TreeNode node) { TreeNode succ node.right; while (succ.left ! null succ.left ! node) { succ succ.left; } return succ; }5. 三道题目的共通技巧与进阶思考5.1 递归与迭代的选择策略在处理树问题时我们通常优先考虑递归解法因为代码简洁更符合树结构的自然表达更容易验证正确性大多数情况下时间复杂度相同但在实际工程中迭代法可能更适合避免递归深度过大导致的栈溢出某些语言对递归优化不足需要更精确控制遍历过程时5.2 BST遍历的顺序魔法这三道题目展示了BST遍历顺序的灵活性修剪BST前序遍历先处理当前节点构建平衡BST类似于二分的中序遍历累加树逆中序遍历右-根-左理解这些遍历顺序的差异是解决BST问题的关键。5.3 实际应用场景举例这些算法在实际中有广泛应用修剪BST数据库索引的范围查询优化平衡BST内存数据库的索引结构实现累加树统计分析和累计分布计算例如在金融系统中累加树可以高效计算账户余额的累计分布在游戏开发中平衡BST可用于快速查找排行榜数据。