如何修剪二叉搜索树使所有节点落在指定区间内？

简化版

利用 BST 性质递归修剪：如果当前节点小于 low，它的左子树也都小于 low，整棵左边丢掉，返回修剪后的右子树；如果当前节点大于 high，它的右子树也都大于 high，整棵右边丢掉，返回修剪后的左子树；否则当前节点保留，递归修剪左右孩子。

详细版

修剪 BST 的目标是删除所有不在 [low, high] 内的节点，同时保留原树中合法节点之间的父子关系。由于 BST 左小右大，当前节点如果太小，则它的左子树更小，必然全部非法；但右子树里可能有合法节点，所以不能直接返回空，而要返回 trimBST(root.right, low, high)。当前节点太大时对称处理。

当当前节点落在区间内时，它应该保留，但它的左右子树仍可能包含越界节点，因此分别递归修剪，并把修剪后的结果重新接回 root.left 和 root.right。时间复杂度最坏 O(n)，空间复杂度 O(h)。

完整版教学

一、修剪不是普通删除节点

普通 BST 删除通常针对一个具体值，要处理叶子、单孩子、双孩子等情况；修剪 BST 是批量保留一个区间。题目真正要你做的是“返回修剪后的新根”，因为原来的根也可能不合法。例如根是 3，区间是 [4, 8]，根 3 必须被丢掉，新根可能来自它的右子树。

原树:
      3
       \
        5
       / \
      4   8

low=4, high=8
修剪后:
      5
     / \
    4   8

如果代码只是在原地删除某些孩子，而不认真处理返回值，就很容易在根节点越界时返回错误的根。

二、为什么 root < low 时可以丢左边

BST 的左子树所有值都小于当前节点。如果 root.val < low，那么左子树所有值满足：

left.val < root.val < low
=> left.val 一定不在 [low, high] 内

所以左子树可以整棵丢掉。但右子树所有值大于 root，有可能进入区间，例如 root=3、low=4 时，右子树里的 5、6 都可能合法。因此这时不是返回 null，而是返回“修剪后的右子树”。这一步是本题最常见的坑。

三、为什么 root > high 时对称返回左子树

如果 root.val > high，右子树所有值都更大，必然也大于 high，可以整棵丢掉；左子树里可能存在合法值，所以返回修剪后的左子树。这个逻辑与上一节完全对称。

当前节点状态	必然非法的部分	仍可能合法的部分	返回
`root.val < low`	当前节点和左子树	右子树	`trim(root.right)`
`root.val > high`	当前节点和右子树	左子树	`trim(root.left)`
`low <= root.val <= high`	无法整棵排除	左右都要修剪	当前节点

表里最重要的是“仍可能合法的部分”。修剪题不是看见越界就返回空，而是要把可能合法的子树接上来。

四、标准递归代码

递归函数的语义是：返回以 root 为根的子树修剪后的新根。语义一旦定好，代码很短。

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;
}

这里的重新赋值很关键：root.left = ... 和 root.right = ... 表示子树修剪后根节点可能发生变化。例如左孩子太小，但左孩子的右子树合法，修剪后就要把这个合法子树接回当前节点。

五、用具体例子追踪返回值

看树 [1,0,2]，区间 [1,2]。根 1 合法，所以保留；修剪左子树 0 时，0 < low，它的左边必然非法，返回修剪后的右子树，也就是 null；修剪右子树 2 时，2 合法，保留。最后根 1 的左孩子被改成 null，右孩子仍是 2。

trim(1):
  1 合法
  left = trim(0)  -> null
  right = trim(2) -> 2
  return 1

结果:
  1
   \
    2

这个过程说明递归返回值不是摆设，它代表“这一片子树修剪后的入口”。很多错误代码会调用 trim(root.left) 但不接收返回值，导致结构没有真正改变。

六、常见误区与追问

修剪 BST 的口令：太小接右，太大接左，合法节点左右重接。

误区：当前节点越界就直接返回 null。 当前节点越界时，另一侧子树仍可能有合法节点，直接返回 null 会误删。
误区：只修剪叶子节点。 越界节点可能在任意层，根节点也可能被替换。
误区：递归修剪左右子树但不把返回值接回去。 子树根可能变化，必须赋给 root.left 或 root.right。
追问：为什么不需要普通 BST 删除的双孩子逻辑？ 因为修剪按区间整体重接子树，不是删除单个值后找后继替换。
追问：复杂度是多少？ 最坏 O(n)，递归栈 O(h)；剪枝能跳过一些整棵非法子树。
追问：区间边界是否保留？ 通常 [low, high] 是闭区间，等于 low 或 high 的节点要保留。

七、加强记忆

修剪 BST 要抓住“返回修剪后的新根”这个递归语义。当前节点太小，左边更小全丢，但右边可能合法，所以返回修剪后的右子树；当前节点太大，右边更大全丢，但左边可能合法，所以返回修剪后的左子树；当前节点合法时，把左右子树分别修剪后重新接回自己。面试时特别强调不要把越界节点直接返回空，也不要忘记接收递归返回值，这两个点最容易暴露理解不深。

简化版

详细版