LeetCode 669. 修剪二叉搜索树

2022-03-09 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 669. 修剪二叉搜索树

题意分析

给一棵二叉搜索树和一个闭区间 [low, high]，要把所有取值落在区间外的节点全部去掉，只留下取值在区间内的节点，最后返回修剪后的树根。

关键在于「修剪」两个字的含义比「筛选」严格得多：留下来的节点不仅数量要对，彼此之间的祖先与后代关系还必须和原树完全一致，也就是说不允许把留下的值重新收集起来另建一棵树。这条要求把很多看似可行的做法直接排除掉了。

边界上有三处要留神。区间是闭区间，值恰好等于 low 或 high 的节点必须保留。修剪后整棵树可能被删空，此时要返回空而不是报错。最容易忽略的是：一个节点被删掉，不代表它的整棵子树都要被删掉——它的某一侧子树里完全可能还藏着落在区间内的节点，必须接上去。

输入还给了一条强信息：这是一棵二叉搜索树，左子树所有值小于根、右子树所有值大于根。凡是给出有序性的题目，都应该先想能不能靠有序性成片地排除候选，而不是逐个检查。

解法：递归裁剪

核心思路

一种直觉做法是把树遍历一遍，找出所有越界的节点，再逐个调用「删除二叉搜索树中的节点」把它们摘掉。这条路能走通，但每删一个有两个孩子的节点都要去找中序后继来顶替，代码量成倍增长，而且删除过程中树的形态一直在变，很难说清正确性。

另一种直觉做法是中序遍历取出所有在区间内的值，再重建一棵树。这条路直接违反题意：重建出来的树虽然值集合正确，但祖先后代关系已经和原树不同了。

瓶颈在于把「修剪」当成了一串独立的删除动作。换个角度看，修剪的结果本身也是一棵树，那就可以用递归定义它：设 trim(node) 返回「以 node 为根的子树修剪之后的新根」，只要每一层都严格按这个语义返回，父层把返回值接回去就自动完成了拼装。

有了这个语义，二叉搜索树的有序性就能成片地砍掉候选。若 node.val < low，那么 node 的整棵左子树的值都比 node 还小，自然全部小于 low，可以整体丢弃，同时 node 自己也要丢；剩下唯一可能有幸存者的地方就是右子树，于是直接返回 trim(node.right)。若 node.val > high 则完全对称，返回 trim(node.left)。若 node 的值落在区间内，node 必然保留，只需把两侧子树各自修剪后接回来。

贯穿全程的不变量是：trim 的返回值永远是一棵合法的、已经修剪完毕的子树的根（可能为空），并且它内部所有节点的相对结构与原树一致。每一层只依赖这条约定，不需要知道更上层的任何信息。

解题步骤

先处理空节点：node 为空时直接返回空。这既是递归的出口，也让上层不必在调用前判空。

若 node.val < low：整棵左子树连同 node 自己一起出局，返回对右子树递归的结果。注意返回的是递归后的右子树而不是原始右子树，因为右子树里同样可能有超过 high 的节点需要继续裁。

若 node.val > high：对称地返回对左子树递归的结果，理由同上。

否则 node 落在闭区间内，一定保留。把 node.left 赋成对左子树递归的结果、node.right 赋成对右子树递归的结果。这两行必须写成赋值，只调用不赋值的话越界的孩子根本没被摘下来。

最后返回 node。整个函数从头到尾只有一种返回语义，所以每一层都能放心地把下层结果当成成品使用。

以 root = [3,0,4,null,2,null,null,1]、low = 1、high = 3 走一遍：这棵树的形状是根为 3，左孩子 0、右孩子 4，节点 0 的右孩子是 2，节点 2 的左孩子是 1。从根 3 开始，3 落在 [1, 3] 内，保留，先递归左边。节点 0 小于 low，于是 0 和它并不存在的左子树一起被丢弃，转而返回 trim(2)。节点 2 落在区间内，保留，它的左孩子递归得到 trim(1)：1 落在区间内且没有孩子，两侧递归都返回空，直接返回节点 1；它的右孩子为空，返回空。于是 trim(2) 返回的是「以 2 为根、左孩子为 1」的子树，这个结果被接到 3 的左指针上。再递归右边：节点 4 大于 high，丢弃 4 和它的整棵右子树，返回 trim(4.left)，而 4 的左孩子为空，所以返回空，3 的右指针被置空。最终得到根为 3、左子树是 2、2 的左孩子是 1、右子树为空的树，序列化后正是 [3,2,null,1]。

代码实现

// 若节点值大于 high，则整棵右子树都被裁掉，返回裁剪后的左子树。
class Solution {
    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;
    }
}

// 若节点值大于 high，则整棵右子树都被裁掉，返回裁剪后的左子树。
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }

    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
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是节点总数。每个节点最多被访问一次，被整体丢弃的子树连访问都不会发生，所以这是一个宽松上界。

空间复杂度：$O(h)$，h 是树高，只消耗递归调用栈；树退化成链时是 $O(n)$，平衡时是 $O(\log n)$。除此之外没有分配任何新节点，修剪完全在原树上完成。

关键点总结

树形问题一旦能把答案本身也描述成一棵树，就该用「递归函数返回处理后的子树根」这个范式；它把删除、拼接这些指针操作全部收敛成一句赋值。

递归函数的返回语义必须一次定死并且每条分支都遵守，这是本题唯一需要保证的东西；三个分支返回的都是「修剪后的子树根」，所以它们可以互相替换、层层嵌套。

有序性的价值在于成片排除：node.val < low 一次性否定了整棵左子树，这是把逐点判断降到线性以下的常见手法，二叉搜索树题里几乎处处可用。

节点越界不等于它的子树全部越界，必须继续往仍有希望的那一侧递归；这是本题最集中的错误来源。

面试视角：面试官很可能先问「为什么不能用删除节点的模板逐个删」，想听的是你意识到删除有两个孩子的节点需要找中序后继、过程中树形会变，正确性难以论证；点破这一点再给出递归返回子树根的写法，思路的高低立判。

面试视角：写完之后常被追问改成迭代版本。答法是先自上而下把根移动到第一个落在区间内的节点，再分别沿左链剪掉小于 low 的部分、沿右链剪掉大于 high 的部分，空间可降到 $O(1)$；能说清这个改写方向，说明你理解的是结构而不是模板。

易错点总结

错误写法：node.val < low 时返回 trim(node.left)，方向写反：root = [3,0,4,null,2,null,null,1]、low = 1、high = 3 → 节点 0 的右子树里还有合法的 2 和 1，却顺着空的左子树返回了空，答案退化成只剩 [3]。

错误写法：节点越界就直接 return null，不再往下递归：同样是上面这组输入 → 节点 0 被删的同时把 2 和 1 一起带走，答案变成 [3]，而正确答案是 [3,2,null,1]。

错误写法：递归调用后忘记赋值，写成两行光秃秃的 trim(node.left, low, high);：root = [1,0,2]、low = 1、high = 2 → 节点 1 的左指针从未被改动，返回的树里仍然挂着越界的 0。

错误写法：把闭区间当成开区间，判断写成 node.val <= low 就丢弃：root = [1,0,2]、low = 1、high = 2 → 值恰好等于 low 的根节点 1 被误删，返回 [2]，正确答案是 [1,null,2]。

错误写法：忘记处理空节点就直接访问 node.val：任何一棵有叶子的树 → 递归到叶子的空孩子时立刻空指针异常。

错误写法：把修剪理解成「收集区间内的值再重建一棵树」：root = [3,0,4,null,2,null,null,1]、low = 1、high = 3 → 值集合 {1, 2, 3} 虽然对，但重建出的树形与原树的祖先后代关系不同，判题不通过。

错误写法：在区间内的分支里只递归一侧、假设另一侧不需要处理：root = [3,0,4,null,2,null,null,1]、low = 1、high = 3 → 若只修左边，越界的 4 会被保留在结果里；若只修右边，越界的 0 会被保留。

错误写法：担心修剪后树不再平衡而额外做一次重建或旋转：任意输入 → 题目只要求删点并保持原有相对结构，任何重排都会改变节点间的祖先关系，属于画蛇添足的错解。

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	只沿一条路径下探，不需要回头拼接子树
701. 二叉搜索树中的插入操作	中等	同为返回子树根的递归范式，但做的是挂上新节点而非摘除
450. 删除二叉搜索树中的节点	中等	只删一个节点，难点在于双孩子情形要用中序后继顶替
98. 验证二叉搜索树	中等	同样围绕取值区间递归，但区间是自上而下收紧的判定条件
938. 二叉搜索树的范围和	简单	同样靠有序性剪掉整棵子树，但只累加数值、不改动树结构
235. 二叉搜索树的最近公共祖先	中等	靠值与两个目标的大小关系决定下探方向，一路不回溯