LeetCode LCR 047. 二叉树剪枝
题目描述
题意分析
节点值只有 0 和 1，要求删除所有不包含 1 的子树。值为 0 的节点如果仍有值为 1 的后代，就必须保留它来连接这些后代；整棵树也可能被剪空。
解法：后序剪枝
核心思路
[!blue]
定义
pruneTree(node)返回以node为根的子树剪枝后的根，整棵子树都应删除时返回空。父节点把这个返回值重新接到对应的孩子指针上，就能同时处理保留和删除两种结果。当前节点是否应删除，取决于左右子树处理后的状态，所以先递归剪左右子树，再判断当前节点。剪枝完成后，非空孩子一定还包含至少一个 1；否则那棵子树已经被递归删除。
因此，只有当前值为 0 且左右孩子都为空时，整棵当前子树才不含 1，应返回空。当前值为 1，或者任意孩子非空，都说明当前子树含有 1，必须返回当前节点。这个规则从叶子逐层成立，也就保证整棵树被正确剪枝。
解题步骤
- 遇到空节点直接返回空，作为递归终止条件。
- 递归处理左右孩子，并把返回值分别赋回
root.left、root.right。- 若当前值为 0 且更新后的左右孩子都为空，返回空；否则返回当前节点。
- 最外层返回的值就是新树根，不能假定原根始终保留。
全零子树会先从叶子开始变空，再逐层使其父节点满足删除条件，一次后序遍历就能完成连续剪枝。即使当前节点为 1，也仍需处理它的孩子，因为下面可能有应删除的全零分支。
代码实现
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)$。
关键点总结
[!green]
- 返回值表示剪枝后的子树根，必须赋回父节点的孩子指针。
- “孩子为空”表示那一侧已经没有需要保留的节点，判断必须发生在孩子处理之后。
- 值为 0 并不必然删除，仍需保留通往值为 1 的后代的路径。
易错点总结
[!yellow]
- 先递归剪孩子，再根据更新后的孩子决定是否删除当前 0 节点。
- 递归返回值必须赋回 left、right，否则删除结果不会接回原树。
- 只有值为 0 且左右都已为空时才删除；根也可能被删掉。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1325. 删除给定值的叶子节点 | 中等 | 同样后序删除不需要的子树，原题按叶子目标值反复剪枝，本题删除整棵不含1的子树。 |
| 1110. 删点成林 | 中等 | 同样删除节点并调整子树连接，原题需要返回保留下来的森林，本题只返回剪枝后的一个根。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！