从“外包别吃零食”到LeetCode669：修剪二叉搜索树的正确打开方式

平时跟组长互相调侃，代码出问题了他还会来一句“你这波有点东西”，让我一度产生了“自己人”的错觉。直到那天，我的手刚伸向工位上的魔芋爽，他的眼神就像扫描仪一样扫过来，淡淡地补了一句：“外包别吃零食”。

合着我在项目里能扛需求、能修Bug、能背锅，就是不能嚼两口零食？我觉得吧，真要管理，不如写清楚“工位禁止食用气味浓烈的零食”，这样大家都服气。现在的说法，听着总有点身份划分的味道。

算了，还是回归正题，聊聊代码。那天刷LeetCode，正好做到第669题“修剪二叉搜索树”（Trim a Binary Search Tree），这题看着简单，动起手来却容易把自己绕进去。题目要求很简单：给定一棵二叉搜索树（BST）和一个区间 [low, high]，你需要“修剪”这棵树，使得所有节点的值都在这个区间内，并且修剪后的树仍然是一棵BST。听起来像是给树理发，但手法不对，很容易就剃成了“地中海”。

我最初的直觉反应是暴力解法：把树中序遍历到一个列表里，过滤掉不在区间内的值，然后用这个列表重新构建一棵平衡的BST。听起来很“优雅”对吧？但仔细一想，这完全违背了题目的本意。这哪是“修剪”，这是“推倒重建”。不仅浪费空间，还完全破坏了原树的结构，在面试里这么干，恐怕会被面试官直接挂掉。

正确的思路其实就四个字：利用性质。BST 最核心的性质就是左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。因此，当我们站在一个节点 root 面前时，通过比较 root.val 和区间 [low, high] 的关系，我们就能判断它的整棵子树的命运。

具体来说，可以分为三种情况：

• 如果 root.val < low，那么当前节点值太小，连同它的整个左子树（值更小）都可以丢弃了。我们只需要继续去它的右子树中寻找符合条件的节点。
• 如果 root.val > high，情况相反，当前节点值太大，连同它的整个右子树（值更大）都可以丢弃。我们只需要继续去它的左子树中寻找。
• 如果 low <= root.val <= high，恭喜，这个节点是“合法居民”。那么我们需要递归地去修剪它的左子树和右子树，并把修剪好的结果重新挂载回来。

基于这个思路，我用 Java 写了一个可以通过的版本：

// 标准 LeetCode 上的 TreeNode 定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class TrimBST {
    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;
    }
}

别看代码就这么几行，里面藏着的坑可不少。第一个常见的错误写法是这样的：

if (root.val < low) {
    root = root.right;
}
if (root.val > high) {
    root = root.left;
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);

这样写看起来好像也对，但问题在于它只是简单地把指针向下移动，并没有把“下层修剪后的结果”正确地传递回上一层。尤其是在处理递归边界时，很容易出现“你以为砍掉了，但实际上还连着”的诡异情况。最稳妥的方式就是像正确解法那样，直接 return trimBST(...)，明确告知上一层：我这整棵子树已经被替换成修剪后的右子树（或左子树）了。

第二个坑是逻辑顺序。有一次我困得不行，写成了这样：

root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);

if (root.val < low) {
    return root.right;
}
if (root.val > high) {
    return root.left;
}
return root;

仔细推敲就会发现不对劲：你先费劲修剪了左右子树，然后才发现当前根节点本身是非法的，于是直接返回 root.right 或 root.left。这时你返回的子树是已经基于一个“非法根节点”修剪过的，虽然某些情况下结果可能侥幸正确，但整个逻辑变得非常别扭，在面试中被追问时很难解释清楚。最干净的做法，还是先判断当前节点的去留，再决定递归的方向。

为了测试方便，我通常还会写一个简单的 main 方法来构建和打印树：

public class TrimBSTDemo {
    public static void main(String[] args) {
        // 手动构建一棵 BST:     3
        //                    /   \
        //                   0     4
        //                    \
        //                     2
        //                    /
        //                   1
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(0);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(1);

        TrimBST solver = new TrimBST();
        TreeNode newRoot = solver.trimBST(root, 1, 3);

        // 中序打印，验证结果是否都在 [1,3] 区间内
        inorder(newRoot); // 预期输出：1 2 3
    }

    private static void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.val + " ");
        inorder(node.right);
    }
}

在这个例子里，原树中包含数值0，修剪区间为 [1,3]。运行后中序遍历输出 1 2 3，证明所有小于1的节点（0）已被正确移除，且剩下的树依然保持BST的有序性。

你当然也可以尝试写一个迭代版本，但对于这种“根据局部节点决定整棵子树命运”的递归操作，递归解法显得非常自然和清晰，栈展开的过程天然地帮我们处理了回溯。强行用迭代，反而可能把思路搞复杂。

这道题给我的启发是：面对树形结构的问题，尤其是像BST这种有强有序性质的结构，别总想着“遍历、收集、重建”的暴力三板斧。多花点时间思考如何利用其原生性质进行就地操作，往往能让代码更简洁、更高效。如果你对这类融合了生活趣事和技术思考的内容感兴趣，欢迎来云栈社区的开发者广场逛逛，那里有不少类似的分享。