新年上班第一天，接到裁员通知！

跑路年年有，裁员也不缺席，偏偏挑在新年上班第一天来个“惊喜盲盒”。

上午我还在工位上捏着开工红包，；中午公司又把午餐安排得明明白白，结果下午一开会，领导一句“公司要裁员”，更离谱的是，居然还挺开心的

网友们也很会补刀：有人说“红包是封口费”，有人说“午餐是散伙饭”，还有人更狠：“这是公司在教你断舍离。”

我觉得吧，成年人的崩溃很安静，成年人的释然也很突然。真轮到自己，先把代码推完，再把简历更新完，主打一个：仪式感给到，退场也要体面点。

我跟你说啊，这题我第一次看到的时候，脑子里第一个画面是花园里剪树篱笆……结果点开一看：哦，原来是“修剪二叉搜索树”，还以为让我拿着剪刀去运维机房呢😅

之前写过一篇吐槽线上性能的文章，数据库那次是 Postgres 把 MySQL 打趴的那个场景，核心思路其实就俩字：取舍。 这题也是一样，你得狠得下心，把不在区间里的那些节点都“裁员”。

你先脑补一下场景哈：有一棵二叉搜索树，节点值乱七八糟，但有个性质你肯定知道——左小右大。现在老板跟你说，只要区间 [low, high] 里的节点，其余都不要，顺便要求： 1）还是一棵合法的 BST 2）不要开一堆新节点，能原地改就原地改

很多同学一上来就说：那我中序遍历一下，拿到一个有序数组，再从数组重建一棵新的 BST 不就行了？ 理论上可以，面试官当场给你一个微笑，然后在评价上写：能做，但不会做。

为啥呢？因为二叉搜索树这个结构本身就已经帮你“排好序”了，你再拐一圈变数组重建，相当于先把手机拆了，然后再按说明书装回去，多此一举。

咱们利用一下 BST 的特性想一想：

• 如果当前节点 val < low，说明它自己太小了，而且它左子树肯定更小，对吧？ 所以这一整个左边都没救了，可以直接扔掉，只去它的右子树里找有没有合法的。
• 反过来，如果 val > high，那它右子树肯定更大，整片右边都超范围了，只能去左子树找。
• 只有在 low <= val <= high 的时候，这个节点才是“编制内员工”，那就把它留下，同时递归去修它的左右子树。

你看，这逻辑一捋，其实特别像人事裁员： 太菜的（小于 low）直接整体优化掉左边部门； 太贵的（大于 high）整体优化掉右边部门； 处在合理薪资区间的，继续详细调整直属团队。

上代码，用 Java 写一版最清爽的递归版，语速有点快你自己跟上哈：

// 面试版标准 TreeNode 定义
classTreeNode{
int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int v) {
this.val = v;
    }
}

publicclassTrimBstDemo{

public TreeNode trimBST(TreeNode root, int low, int high){
// 1. 空树，直接返回
if (root == null) {
returnnull;
        }

// 2. 当前节点太小，丢掉自己和左子树，去右子树继续找
if (root.val < low) {
return trimBST(root.right, low, high);
        }

// 3. 当前节点太大，丢掉自己和右子树，去左子树继续找
if (root.val > high) {
return trimBST(root.left, low, high);
        }

// 4. 落在区间内，继续修剪左右孩子
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

// 5. 自己是合格的根，留在编制里
return root;
    }
}

这段其实很有意思： 你注意看，真正“修剪”的动作，就是在 4 那两行 root.left = ...、root.right = ...，递归会不断把不合格的子树剪掉，把合格的挂回到当前节点上。 而 2、3 那两个分支，其实是在“往上冒”：当当前节点根本不该存在时，直接把“我”换成“我某个合法子树”的根节点。

你要是还觉得有点虚，可以拿个简单例子糊一下：

比如原来的树中序遍历是：1, 2, 3, 4, 5, 6, 7，区间是 [3, 5]。

• 跑到 2 的时候，2 < 3，整棵以 2 为根的左子树都扔掉，只保留右边；
• 跑到 6 的时候，6 > 5，整棵以 6 为根的右子树扔掉，只保留左边； 最后留下来的，只会是 3,4,5 这块连起来的一棵小 BST，结构也还是合法的。

顺手再给你补一段构建和打印的测试代码，你可以在本地随便跑跑看效果，不要光用眼睛“运行”：

publicclassTrimBstDemo{

// 上面那个 trimBST 省略，自行粘一起

publicstaticvoidmain(String[] args){
        TrimBstDemo demo = new TrimBstDemo();

// 手搓一棵简单 BST：
//       4
//     /   \
//    2     6
//   / \   / \
//  1  3  5  7
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);

int low = 3, high = 6;
        TreeNode newRoot = demo.trimBST(root, low, high);

// 打个中序看看结果是不是 3 4 5 6
        inorder(newRoot);
    }

privatestaticvoidinorder(TreeNode root){
if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

你本地跑一下，会看到输出是：3 4 5 6，这就对了。 注意几个边界情况，面试官有时候爱拿这个做加分题的：

• 整棵树所有节点都小于 low，那最后会返回 null，也就是一棵空树。
• 整棵树所有节点都大于 high，同理也是 null。
• low 和 high 本身不保证在树里存在，这没关系，只要保证区间合法就行。

还有个容易翻车的小细节：千万别在递归里面又手贱 new 新节点，那就不是“修剪”了，是“抄一份新的出来”，面试官一般会直接问你一句： “那你这个算法空间复杂度是不是又回到 O(n) 了？” 咱这版是就地改指针，额外空间主要就是递归栈，平均算个 O(h)——h 是树高，能答到这儿基本就稳了。

行，就到这儿吧，我这会儿还得回去给实习生解释什么是前序遍历，他刚刚把中序和层序又认反了……