LeetCode 814. 二叉树剪枝

2025-04-23 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 814. 二叉树剪枝

题意分析

给的是一棵节点值只有 0 和 1 的二叉树，要把「整棵子树里一个 1 都没有」的部分全部摘掉，返回剪完之后的树根。

题面的措辞是「移除所有不包含 1 的子树」，这句话有个陷阱：判断依据是整棵子树，不是单个节点。一个值为 0 的节点，只要它的后代里还藏着一个 1，就必须留下来当路径上的连接点。

反过来讲，同一个条件还有更强的一层含义：如果某棵子树该被删，那么它内部的每一棵子树也都该被删，因为它们同样一个 1 都没有。所以「删掉整棵子树」和「自底向上逐层删空」是等价的，这为递归留下了空间。

边界上要考虑：整棵树全是 0（答案是空树，包括根也要删）、整棵树全是 1（原样返回）、单节点树、以及值为 0 但一侧子树保留另一侧被删空的情况。

解法：后序遍历剪枝

核心思路

暴力做法是对每个节点单独跑一次「这棵子树里有没有 1」的查询，有就留、没有就整棵摘掉。每次查询要遍历整棵子树，n 个节点各查一次，最坏是 $O(n^2)$，链状树上尤其糟糕。

瓶颈在于「子树里有没有 1」被反复重算：查根的时候扫了一遍全树，查根的孩子时又把同一批节点扫了一遍。而这个信息其实完全可以在一次遍历里自底向上攒出来——一个节点的答案只取决于它自己的值和两个孩子的答案。

观察到「删掉」这个动作可以用返回值表达：让递归函数返回「这棵子树剪完之后的根」，删掉就是返回空。父节点拿到返回值后重新挂到自己的孩子指针上，删除就自动完成了，不需要显式的指针操作或父指针。

于是得到显式的不变量：pruneTree(node) 返回的一定是一棵「每个节点的子树里都至少含一个 1」的树，且它是原子树剪枝后的唯一结果；当原子树里一个 1 都没有时返回空。

有了这条不变量，当前节点的判断就非常简单。递归完成后，node.left 和 node.right 已经是剪好的子树。如果两个孩子都是空，说明左右两侧原本都不含 1；此时只要 node.val == 0，整棵以 node 为根的子树也不含 1，返回空；只要有一个孩子非空，或者 node.val == 1，这棵子树就含 1，原样返回 node。

必须是后序：当前节点的去留依赖孩子剪完之后的形态，先序或中序都拿不到这个信息。

解题步骤

空节点直接返回空。这是递归出口，同时也让「孩子不存在」和「孩子被剪掉」统一成同一种表示，后面判断时不用分两种情况。

先递归处理左子树，并把返回值重新赋给 node.left。赋回去这一步是删除动作真正发生的地方，只调用不赋值等于什么都没做。

同样递归处理右子树并赋回 node.right。

检查 node.val == 0 && node.left == null && node.right == null，成立就返回空。三个条件缺一不可：值为 0 说明自己不贡献 1，两个孩子都空说明后代里也没有 1（因为不变量保证保留下来的子树必含 1），合起来才能断定整棵子树可删。

否则返回 node 本身，把它交还给上层重新挂载。

最外层直接返回递归结果，不要假设根一定活着——全 0 的树最终会返回空。

以 root = [1, null, 0, 0, 1] 走一遍：这棵树的形状是根 1 没有左孩子，右孩子是 A(0)；A 的左孩子是 B(0)，右孩子是 C(1)；B 和 C 都是叶子。

递归先下到根的左边，null 直接返回空，根的左指针仍是空。接着进入右子树 A。

在 A 内部先处理 B：B 的两个孩子都是 null，递归各自返回空；判断 B.val == 0 且两孩子皆空，条件成立，返回空。于是 A.left 被赋成 null，B 被摘掉。

再处理 C：两个孩子递归返回空，但 C.val == 1，第一个条件就不成立，返回 C 自身。A.right 仍然是 C。

回到 A 自己：A.val == 0 成立，A.left == null 成立，但 A.right 是 C 不为空，整体条件不成立，返回 A。根的右指针仍是 A。

最后回到根：根的值是 1，直接返回自己。最终树形是 [1, null, 0, null, 1]，只有 B 被剪掉。

再看全 0 的用例 root = [0, 0, 0]：两个叶子 0 各自返回空，根的两个孩子都被置空，根自己值为 0 且两孩子皆空，返回空——整棵树被剪光，函数返回空树。

代码实现

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.val == 0 && root.left == null && root.right == null) {
            return null;
        }
        return root;
    }
}

func pruneTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left = pruneTree(root.Left)
    root.Right = pruneTree(root.Right)
    if root.Val == 0 && root.Left == nil && root.Right == nil {
        return nil
    }
    return root
}

复杂度分析

时间复杂度：$O(n)$，n 是节点总数。每个节点恰好进入递归一次，函数体内只有常数次比较和两次赋值，没有任何重复扫描。

空间复杂度：$O(h)$，h 是树高，全部来自递归调用栈。平衡树上是 $O(\log n)$，退化成链时是 $O(n)$；算法没有申请任何额外的数组或集合，剪枝是在原树上原地完成的。

关键点总结

「自顶向下判断」和「自底向上汇总」是树上问题的两条路，选错方向就会陷入重复计算。凡是当前节点的决策依赖整棵子树的聚合信息，就必须走后序，让孩子先把结论算好再回来。

用返回值表达「删除」，是链表和树的删除类问题里最省心的写法。递归函数返回「处理后的新根」，父节点接住并重新赋值，就不需要维护父指针、也不需要区分「删的是左孩子还是右孩子」。

递归调用必须赋回去，这条在 pruneTree(root.left) 上体现得最直白。只调用不赋值的写法看起来很像对的，但它一个节点也删不掉，是这类题最高频的失分点。

空节点和被剪空的子树用同一种表示（都是 null），使得判断条件只需要看孩子指针是否为空，不必额外记录「这个孩子是本来就没有还是被我删了」。统一表示能省掉一整类分支。

面试视角：常见追问是「如果值不止 0 和 1，要删掉所有和为 0 的子树呢」。答案是把返回值从「新根」扩展成「新根 + 子树和」，或者用一个额外的后序函数先算和；核心的后序框架完全不变。第 1325 题的「反复删除值为 target 的叶子」也是同一个模板。

面试视角：写完后主动指出「根节点也可能被剪掉，所以函数签名必须返回 TreeNode 而不是 void」，能说明你考虑过全 0 的退化输入，这是面试官最想听到的边界意识。

易错点总结

错误写法：前序遍历，一进节点就判断 val == 0 并整棵摘掉。用例 [1, null, 0, 0, 1] → 走到 A(0) 时直接把它连同子树删掉，而它的右孩子 C 是 1，结果返回 [1]，正确答案是 [1, null, 0, null, 1]。

错误写法：递归调用了却没有把返回值赋回孩子指针，写成 pruneTree(root.left);。用例 [1, null, 0, 0, 1] → 递归照常跑完，但树的指针一个都没改，返回的还是原树 [1, null, 0, 0, 1]，叶子 B 没被剪掉。

错误写法：删除条件写成 val == 0 就返回空，不检查孩子。用例 [1, null, 0, 0, 1] → A 的值为 0 被直接删掉，连带把 C 这个 1 也丢了，返回 [1] 而不是 [1, null, 0, null, 1]。

错误写法：判断孩子时用递归前的原始指针，而不是剪枝后的结果。用例 [1, null, 0, 0, 1] 的子树 A → 剪枝前 A.left 指向 B 不为空，条件不成立所以保留 A（结果碰巧对），但换成 [0, 0, 0] 时根的两个孩子在剪枝前都非空，根被误判为要保留，返回 [0] 而不是空树。

错误写法：函数签名写成 void，靠在父节点里手动断开孩子来实现删除。用例 [0, 0, 0] → 整棵树都该删，但根没有父节点可以断开它，函数无法表达「返回空树」这个结果。

错误写法：只把当前的 0 叶子摘掉，跑一趟就结束，不考虑摘完会产生新叶子。用例 [1, 0, 0, 0, 0]（根 1，左右孩子都是 0，左孩子又带两个 0 叶子）→ 一趟扫描删掉最底层的两个 0 叶子和右边那个 0 叶子，但左孩子这时才变成 0 叶子却没人再处理，返回 [1, 0] 而不是 [1]。

错误写法：把删除条件里的 && 写成 ||。用例 [1, null, 0, 0, 1] → C 的值虽然是 1，但它两个孩子都空，left == null 这一支单独成立就被删掉，A 随后也被删掉，返回 [1] 而不是 [1, null, 0, null, 1]。

错误写法：递归出口漏写，直接访问 node.val。用例任何有单侧孩子的树，例如 [1, null, 0, 0, 1] → 处理根的左孩子时对 null 取 val，抛空指针异常。

相似题目

题目	难度	考察点
1110. 删点成林	中等	删除后要收集断开产生的多个新根，返回的是森林而非单棵树
1325. 删除给定值的叶子节点	中等	删除会级联产生新叶子，考察后序天然完成了「反复删」这件事
669. 修剪二叉搜索树	中等	剪枝依据是值域区间，可借助 BST 有序性整条子树跳过
LCR 047. 二叉树剪枝	中等	同题的另一入口，适合用来复核返回值赋回这一步是否写对