平时跟组长打打闹闹的，以为他把我当自己人，直到我伸手去拿魔芋爽，组长说外包不能吃零食

奇葩规定年年有。昨天我在工位上伸手去拿一包魔芋爽，平时跟组长还互相开黑、互怼表情包，我觉得他都快把我当“自家人”了。结果他抬头来一句：“外包不能吃零食。”

我觉得吧，管理真要管就管产出，别盯着我嘴巴。毕竟程序员的快乐很简单：需求少一点，零食多一点，别让我写着写着，连魔芋爽都得走审批流。

算法题：修剪二叉搜索树

我跟你说啊，修剪二叉搜索树这个题，是真有点像过年回老家被爸妈催婚 —— 哪儿不顺眼就给你“修剪”两句，最后整个家谱都被改造了。

那天晚上我正准备打两把游戏，产品在群里艾特我，说“东哥，线上那个配置范围不对的 bug 明天得修完”。我一看需求，大概意思就是：有一棵二叉搜索树，里面节点的值乱七八糟，现在业务只认 [low, high] 这个区间，区间外的统统都得砍掉，但还得保证它还是个二叉搜索树，长得不能变形，你说气不气人。

我当时脑子里第一个反应是：啊这不就是修剪二叉搜索树嘛，面试原题，终于能光明正大抄…咳咳，复用一下自己的刷题积累了。

你们先想象一下场景哈，正常的二叉搜索树是这样的： 左边都比根小，右边都比根大，这个规则一路递归下去。所以你在一个节点上，只要一看它的值跟区间 [low, high] 的关系，其实能顺带把一整个子树给干掉，这就是爽的地方。

我当时坐在电脑前，嘴里念叨着：“小于 low 的，整棵左子树都是废的；大于 high 的，整棵右子树都是废的。”想明白这个，代码基本上就写完一大半了。

我先随手用 Python 写了个节点结构，别问为啥自己写，问就是线上那套对象太丑了，看着心烦：

classTreeNode:
def__init__(self, val: int,
                 left: 'TreeNode | None' = None,
                 right: 'TreeNode | None' = None):
        self.val = val
        self.left = left
        self.right = right

核心的修剪逻辑其实就几行，但一定要拎清楚三个分支，不然很容易绕晕。那会儿我边写边碎碎念：

1. 如果这个节点都不存在，那修个锤子，直接返回 None。
2. 如果 root.val < low，说明这个点太小了，左子树比它还小，整片都不用看，直接去右子树找有没有能留下的。
3. 如果 root.val > high，反过来，右边全比它大，也是全废，只能去左边找。
4. 剩下的就是 low <= root.val <= high，这个节点可以保留，但是它的左右子树还得继续修剪。

然后我就写成了这样：

deftrim_bst(root: TreeNode | None,
             low: int,
             high: int) -> TreeNode | None:
if root isNone:
returnNone

# 当前节点太小，直接扔掉它和它的左子树
if root.val < low:
return trim_bst(root.right, low, high)

# 当前节点太大，扔掉它和它的右子树
if root.val > high:
return trim_bst(root.left, low, high)

# 在区间里，就递归修剪两边
    root.left = trim_bst(root.left, low, high)
    root.right = trim_bst(root.right, low, high)
return root

你看，逻辑其实特别像我们删工作群里的人：

• 小于 low 的是“太 junior 了”，一整片左边都不考虑，往右看；
• 大于 high 的是“太贵了”，一整片右边先请出群，往左看；
• 能留下来的，左右再各自筛一遍。

当时写完我还特意打了个小 demo 验证一下，因为这类题最坑的是“看起来没问题，实际上树结构已经变得面目全非了”：

definorder(root: TreeNode | None):
ifnot root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)

root = TreeNode(5,
    left=TreeNode(3,
        left=TreeNode(2),
        right=TreeNode(4)
    ),
    right=TreeNode(8,
        left=TreeNode(6),
        right=TreeNode(9)
    )
)

new_root = trim_bst(root, 3, 8)
print(inorder(new_root))  # 理论上应该是 [3,4,5,6,8]

这行 inorder 打出来的结果是有序的，说明 BST 的特性还在；再看数值都在 [3, 8] 里，说明修剪成功。那一刻我心情非常平静，仿佛给测试同学画了一个完美的锅盖，你随便砸我都不怕那种。

顺便说一句，很多同学下意识会这么干： “我先中序遍历全部拉成一个有序数组，然后再过滤区间，最后用数组重新建一棵树。” 听起来还挺优雅对吧，但时间空间全炸。你原本一棵树 O(n) 就能搞定的事情，硬是搞成了“遍历一次 + 重建一次”，而且中间还占了一坨数组，内存监控看了都想掐你。

修剪这个递归法，其实就走一遍树，每个节点最多访问一次，不会额外开很大空间（除了递归栈），复杂度就是正儿八经的 O(n)。对比一下你就知道哪个更接近“工程思维”了。