LeetCode 814. 二叉树剪枝
题目描述
题意分析
二叉树节点值只有 0 和 1，删除所有不含 1 的子树。需要判断的是整棵子树，不是当前节点的值：值为 0 的节点若有后代为 1，就必须保留它来连接这些后代。若整棵树不含 1，返回空树。
解法：后序遍历剪枝
核心思路
[!blue]
让
pruneTree(root)返回当前子树剪枝后的根：原子树不含 1 时返回空；否则返回当前根，同时它的左右子树都已完成剪枝。父节点只需接回这两个返回值，就能把被删子树的链接断开。先递归处理左右孩子，再决定是否保留当前节点。根据递归的含义，处理后的孩子为空，说明对应原子树不含 1；孩子非空，则说明其中一定保留着至少一个 1。因此“当前值为 0，且处理后的左右孩子都为空”恰好等价于“当前整棵子树不含 1”，此时返回空即可。
其余情况都必须保留：当前值为 1 时，节点本身就满足要求；当前值为 0 但仍有非空孩子时，它是通向某个 1 的路径。这个判断从叶子向根逐层成立，所以一次后序遍历就能剪掉所有纯零子树，无需反复扫描整棵树。
解题步骤
- 当前节点为空，直接返回空。
- 递归剪枝左子树，把返回值写回
root.left；对右子树做同样处理。- 若当前值为 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)$。代码直接修改原树链接，不创建新节点。
关键点总结
[!green]
- 递归返回的是剪枝后的子树根，空返回值同时表达“整棵子树不含 1”。
- 先处理孩子，再检查当前节点，才能用孩子是否为空代替重复查找子树中是否有 1。
- 判断中保留值为 1 的叶子，也保留连接到 1 的零值祖先。
易错点总结
[!yellow]
- 仅凭当前值为 0 就删除，会一并丢掉需要保留的后代。
- 必须先接回剪枝后的孩子，再判断是否成为零叶子；使用原孩子状态会漏掉逐层剪空的子树。
- 只递归调用却不写回返回值，不会断开父节点指向已删子树的链接。
- 不能假定原根始终存在。单个零节点或全零树都应返回空，单个一节点则必须保留。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1325. 删除给定值的叶子节点 | 中等 | 同样后序删除不需要的子树，原题按叶子目标值反复剪枝，本题删除整棵不含1的子树。 |
| 1110. 删点成林 | 中等 | 同样删除节点并调整子树连接，原题需要返回保留下来的森林，本题只返回剪枝后的一个根。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！