leetcode669.修剪二叉搜索树：递归法利用有序性精准剪枝

一、题目深度解析与BST特性应用

题目描述

给定一棵二叉搜索树（BST）和一个值区间[low, high]，修剪BST使得所有节点的值都落在该区间内。修剪后的树必须保持BST的性质，且不能改变原有节点的相对位置关系。

BST的核心特性应用

二叉搜索树的重要性质：

• 左子树所有节点值 < 根节点值
• 右子树所有节点值 > 根节点值
• 中序遍历结果为严格递增序列

这些特性使得我们可以通过比较节点值与区间边界的大小关系，高效决定保留或舍弃哪些子树，从而实现精准剪枝。

二、递归解法的核心实现与逻辑框架

完整递归代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null){  // 终止条件：空节点直接返回return null;}// 情况1：当前节点值大于high，整棵右子树及当前节点都应舍弃if(root.val > high){return trimBST(root.left, low, high);  // 仅保留左子树修剪结果}// 情况2：当前节点值小于low，整棵左子树及当前节点都应舍弃if(root.val < low){return trimBST(root.right, low, high);  // 仅保留右子树修剪结果}// 情况3：当前节点值在区间内，递归修剪左右子树root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;  // 返回修剪后的当前节点}
}

核心设计解析：

1. 递归终止条件：

   • 若root为空，直接返回null

2. 三种剪枝情况：

   • 情况1：root.val > high
     当前节点及其右子树所有节点值均大于high，直接舍弃，递归处理左子树
   • 情况2：root.val < low
     当前节点及其左子树所有节点值均小于low，直接舍弃，递归处理右子树
   • 情况3：root.val ∈ [low, high]
     当前节点保留，递归修剪左右子树

3. 递归路径选择：

   • 根据当前节点值与区间边界的关系，选择性递归左子树或右子树
   • 确保每次递归处理的子树中可能存在符合条件的节点

三、核心问题解析：递归逻辑与剪枝策略

1. BST特性如何指导剪枝决策

关键性质推导：

• 若root.val > high，则其右子树所有节点值均 > high → 整棵右子树可舍弃
• 若root.val < low，则其左子树所有节点值均 < low → 整棵左子树可舍弃
• 若root.val ∈ [low, high]，则当前节点必须保留，但其左右子树可能仍需修剪

数学表达式：

设当前节点为root，则：

• 当root.val > high时，修剪结果 = trimBST(root.left, low, high)
• 当root.val < low时，修剪结果 = trimBST(root.right, low, high)
• 否则，修剪结果 = 当前节点 + 修剪后的左右子树

2. 递归逻辑的切入点

递归步骤拆解：

1. 终止条件检查：当前节点为空时返回null
2. 值比较决策：
   • 若当前节点值超出区间，直接舍弃并递归处理另一侧子树
   • 若当前节点值在区间内，递归修剪左右子树
3. 子树重构：将修剪后的左右子树连接到当前节点
4. 返回结果：向上层返回修剪后的当前子树

关键代码逻辑：

// 舍弃右子树，递归处理左子树
if(root.val > high) return trimBST(root.left, low, high);// 舍弃左子树，递归处理右子树
if(root.val < low) return trimBST(root.right, low, high);// 保留当前节点，递归修剪左右子树
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);

四、递归流程深度模拟：以示例BST为例

示例BST结构与修剪区间：

        3/ \0   4\2/1

修剪区间：[1, 3]

递归调用过程：

1. 根节点3的递归：

   • 比较：3 ∈ [1, 3] → 保留当前节点
   • 递归左子树0
   • 递归右子树4

2. 左子树0的递归：

   • 比较：0 < 1 → 舍弃当前节点及其左子树
   • 递归右子树2

3. 节点2的递归：

   • 比较：2 ∈ [1, 3] → 保留当前节点
   • 递归左子树1
   • 递归右子树null

4. 节点1的递归：

   • 比较：1 ∈ [1, 3] → 保留当前节点
   • 左右子树均为null → 返回节点1

5. 右子树4的递归：

   • 比较：4 > 3 → 舍弃当前节点及其右子树
   • 递归左子树null → 返回null

修剪后的BST结构：

        3/2/1

五、算法复杂度分析

1. 时间复杂度

• O(n)：每个节点最多访问一次，n为树的节点数
• 递归过程中每个节点执行常数级判断，总时间线性于节点数

2. 空间复杂度

• O(h)：h为树的高度（递归栈深度）
  • 平衡树：h=logn，空间复杂度O(logn)
  • 最坏情况（链表树）：h=n，空间复杂度O(n)

3. 与迭代解法对比

方法	时间复杂度	空间复杂度	代码简洁度
递归法	O(n)	O(h)	高
迭代法	O(n)	O(h)	低

六、核心技术点总结：递归剪枝的三大关键

1. BST有序性的充分利用

• 路径压缩：根据节点值与区间的关系，每次递归排除一半子树
• 剪枝策略：直接舍弃不符合条件的整棵子树，无需遍历其中节点

2. 递归设计的精妙之处

• 自底向上重构：递归返回值自然实现子树重构
• 简洁逻辑：通过三种情况处理所有可能的节点值分布

3. 区间边界的数学意义

• 闭区间保证：[low, high]确保包含边界值的节点被保留
• 传递不变性：递归过程中始终保持区间参数不变，确保剪枝一致性

七、常见误区与优化建议

1. 错误的剪枝判断

• 误区：使用root.val >= high或root.val <= low作为剪枝条件

  // 错误示例：可能误删边界值节点
  if(root.val >= high) return trimBST(root.left, low, high);
  

• 正确逻辑：严格使用>和<，确保边界值节点被保留

2. 不必要的子树遍历

• 优化点：当节点值超出区间时，直接舍弃整棵子树
• 错误做法：递归遍历超出区间的子树后再判断

  // 低效做法：浪费时间遍历无效子树
  TreeNode left = trimBST(root.left, low, high);
  if(root.val > high) return left;
  

3. 迭代实现的可行性

// 迭代法框架（代码不完整，仅作示意）
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {TreeNode node = stack.pop();if(node.val > high) {// 处理左子树} else if(node.val < low) {// 处理右子树} else {// 处理左右子树}
}

• 优势：避免递归栈溢出风险
• 劣势：代码复杂度显著增加，需手动维护栈结构

八、总结：递归剪枝是BST特性的最佳实践

本算法通过递归方式，充分利用BST的有序性，将修剪操作转化为高效的子树排除问题。核心在于：

1. 数值比较指导剪枝决策：根据节点值与区间边界的关系，直接舍弃无效子树
2. 三种剪枝场景处理：覆盖所有可能的节点值分布情况
3. 递归实现子树重构：通过递归返回值自然实现树结构的调整

理解这种递归解法的关键在于把握BST的数值分布特性，将修剪问题转化为区间定位问题。在实际工程中，这种利用数据结构固有特性的优化思路，是提升算法效率的重要方向。