LeetCode LCR 047. 二叉树剪枝
目录
题目描述
题意分析
题目目标：给定一棵所有节点值都是 0 或 1 的二叉树，删掉所有不包含 1 的子树，返回处理后的树根。换句话说，最终保留下来的每一个节点，其自身或后代中至少存在一个 1。
核心约束：删除的判定依赖整棵子树的信息而不是节点自身——一个值为 0 的节点，只要后代里有 1 就必须留下。这种"父节点的结论依赖子节点的结论"的依赖方向，说明信息必须自底向上汇总。
边界处理：整棵树可能被剪光，此时要返回空而不是原根；叶子是判定的起点，值为 0 的叶子直接被删；值为 1 的节点无论后代如何都保留；树本身也可能为空。
实现取舍：剪枝是链式的——删掉一个叶子后，它的父节点可能因此变成新的叶子并接着被删。所以必须保证父节点的判定发生在两个孩子都处理完之后，否则会漏剪。
解法：深度优先搜索
核心思路
直觉上的做法是反复扫描整棵树，每一轮删掉当前所有值为 0 的叶子，直到某一轮没有任何删除为止。这是对的，但一条长度为
n的全零链要扫n轮，代价 $O(n^2)$，而且"反复直到稳定"这种写法在面试白板上既啰嗦又容易出错。
瓶颈在于每一轮只削掉最外面一层。观察链式剪枝的传播方向：删除总是从叶子开始，向上传染到父亲。既然结论从下往上流动，那就让递归的返回值承担这个流动——只要一次后序遍历，每个节点在自己被判定时，两个孩子的最终形态就已经确定了。
由此显式定义递归的语义（这是本题唯一需要想清楚的东西）：pruneTree(node)返回"以node为根的子树剪枝完成后的新根"，若整棵子树都该被删除则返回空。这个定义同时覆盖了空、被删、保留三种情况，调用方只需把返回值赋回原来的孩子指针即可。
有了这个语义，判定规则就极简：先递归处理左右孩子并把返回值写回，此时node.left、node.right已经是剪枝后的结果；如果node.val == 0且两个孩子都已为空，说明这棵子树里一个 1 都不剩，返回空；否则返回node本身。链式传播由递归的返回顺序自动完成，不需要任何循环。
解题步骤
- 递归入口先处理空节点，直接返回空。为什么这一步能兜住所有边界：它既是递归的终止条件，也顺手处理了整棵树为空的输入，后续代码可以放心地解引用
root。- 执行
root.left = pruneTree(root.left)，把左子树的剪枝结果写回。为什么必须写回而不是只调用：递归返回的可能是空，只有赋值回去才能真正切断被删的子树；只调用不赋值等于什么也没做。- 同样处理右子树。为什么两次递归都要在判定之前完成：当前节点是否该删取决于孩子剪完之后的形态，提前判定就会用到过时的信息，漏掉链式传播。
- 判定
root.val == 0 && root.left == null && root.right == null时返回空。为什么三个条件缺一不可：值为 1 说明本身含 1 必须保留；任一孩子非空说明后代里还有 1（否则那个孩子早就被剪掉了），也必须保留。- 否则返回
root，把自己交还给父亲。为什么返回值语义要在所有分支上保持一致：父亲拿到的必须永远是"剪枝后的子树根或空"，一旦某个分支返回了别的东西（比如返回孩子），整棵树的结构就串了。- 以
具体用例：树[1, null, 0, 0, 1]（根 1 只有右孩子 0，记作 A；A 的左孩子是 0，记作 B；A 的右孩子是 1，记作 C）走一遍。递归到 B：它的左右孩子都是空，val == 0且孩子全空，返回空，于是 A 的左指针被置空。递归到 C：孩子全空但val == 1，返回 C 自身，A 的右指针保持指向 C。回到 A：此时左孩子为空、右孩子是 C 非空，虽然val == 0但条件不满足，返回 A。回到根：val == 1，返回根。最终树是[1, null, 0, null, 1]，B 被剪掉而 A 因为后代含 1 被保留。再看链式情形，树[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)$。凭什么：每个节点只被递归访问一次，访问时做的是常数次指针赋值与比较，链式剪枝靠返回顺序完成而不是靠重复扫描。
- 空间复杂度：$O(h)$，
h为树高，最坏（链状树）为 $O(n)$。凭什么：没有申请任何额外容器，唯一开销是递归调用栈，深度等于树高。
关键点总结
- 凡是"父节点的结论依赖子树整体信息"的树形问题，都应当用后序遍历，并把结论编码进递归的返回值里；先想清返回值代表什么，代码几乎是自动写出来的。
node.child = dfs(node.child)这个"递归结果写回指针"的写法是所有结构性修改树的题目的统一模板（剪枝、删点、修剪区间都适用），比在父节点里手动判断该不该置空要稳得多。- 链式连锁反应不需要循环到稳定：只要判定发生在孩子已经定型之后，一次后序遍历就把连锁效应全部吃掉。
- 判定条件里"孩子为空"之所以能代表"孩子那边没有 1"，靠的是递归的归纳保证——每一步都要能说出这句话，才算真正理解了后序的力量。
- 面试视角：面试官想看的是你能否准确说出递归函数的契约。开口先讲"我定义
pruneTree(node)返回剪枝后的子树根，可能为空"，再解释为什么必须后序，最后补一句"根也可能被剪掉，所以返回值必须交给调用方而不能假设根一直在"，基本就拿满了。
易错点总结
- 错误写法：只调用
pruneTree(root.left)而不把返回值赋回 → 树[1, 0, 0]时两个叶子的删除结果丢失，返回的树仍是[1, 0, 0]，一个节点都没剪掉。- 错误写法：把判定写在两次递归之前（前序） → 树
[0, 0, 0]时根在孩子还没被剪时判定，此时孩子非空所以根被保留，返回[0]而不是空树，链式传播被切断。- 错误写法：判定条件漏掉
root.val == 0，写成只要孩子全空就删 → 树[1]时根是叶子且值为 1，却被误删，返回空树。- 错误写法：判定条件漏掉孩子判空，写成只要
val == 0就返回空 → 树[0, null, 1]时根被删掉，值为 1 的右孩子跟着丢失，返回空树而不是[0, null, 1]。- 错误写法：条件里的
&&写成||→ 树[1, null, 0, null, 1]中值为 1 的叶子因为"孩子为空"这半边成立而被删除，含 1 的节点被误剪。- 错误写法：值为 0 的节点直接返回它的某个非空孩子来"跳过自己" → 树
[1, null, 0, null, 1]会被压成[1, null, 1]，题目要求的是删除整棵不含 1 的子树，而不是压缩路径。- 错误写法：缺少
root == null的入口判断 → 空树输入时访问root.val直接空指针异常，Go 里同样 panic。- 错误写法：假设根一定不会被删，直接
return root→ 树[0]或[0, 0, 0]时应返回空树，实际返回了一个孤零零的 0 节点。- 错误写法：改写成反复扫描删叶子直到不再变化 → 结果正确但一条 $10^4$ 长的全零链要扫 $10^4$ 轮，代价升到 $10^8$ 级别，同时循环终止条件极易写成死循环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1325. 删除给定值的叶子节点 | 中等 | 判定值由参数给出，同样靠后序触发链式删除 |
| 669. 修剪二叉搜索树 | 中等 | 剪枝依据是值域区间，可借助有序性只递归一侧 |
| 450. 删除二叉搜索树中的节点 | 中等 | 删除单个内部节点需要找后继补位，重接逻辑更复杂 |
| 226. 翻转二叉树 | 简单 | 同为结构性修改，但改的是左右指针而非删除 |
| 617. 合并二叉树 | 简单 | 递归返回新节点，考察两棵树同步下降的写法 |
| 110. 平衡二叉树 | 简单 | 同样自底向上汇总，但返回值要同时携带高度与结论 |