LeetCode 补充题 118. 二叉树的叶子父节点剪枝
题目描述
[!green]
牛客原题： ✅ 补充题 118. 二叉树的叶子父节点剪枝
给你一棵二叉树的根节点
root，请移除操作开始前的所有叶子节点。你只能删除某个原始叶子的父节点，删除时该父节点的整棵子树都会被移除。返回能够保留最多节点的结果树。新产生的叶子节点不需要继续删除。
如果树只有一个节点，约定返回空树；如果输入为空树，仍返回空树。
示例 1：
输入：
root = [1,2,3,4,5,6,7]
输出：[1]
解释： 原始叶子为 4、5、6、7，必须删除其父节点 2、3，根 1 保留。
示例 2：
输入：
root = [1,2,3,null,null,4]
输出：[]
解释： 2 是原始叶子，所以其父节点 1 必须整棵删除，无法单独保留右侧分支。
示例 3：
输入：
root = [1]
输出：[]
解释： 采用单节点直接删除的边界约定。
示例 4：
输入：
链表状二叉树 1→2→3→4，每条边均为左孩子边
输出：1→2
解释： 原始叶子只有 4，删除其父节点 3 的子树即可。2 虽然变成新叶子，也应保留。
提示：
- 采用节点数不超过
1000的递归实现版本。 - “原始叶子”以操作前的树为准；本轮剪枝形成的新叶子保留，不级联删除。
- 允许原地修改子指针。
题意分析
删除操作的对象是原始叶子的父节点，并连同其整棵子树一起移除。对每个原始叶子，这个父节点覆盖的子树都无法保留；所有这些必删区域之外的节点才是能够保留的部分。
因此不需要反复剪树，也不需要比较多套删除方案。只需在原始结构上识别必删子树，并保留其他节点。
解法：先判断原始叶子再剪枝
核心思路
[!blue]
进入当前节点时，先检查它是否为空、是否是叶子，或是否具有叶子孩子。空树和单节点按题面约定返回空；只要某个孩子是原始叶子，当前子树属于必删区域，直接返回空即可。
若当前节点可以保留，再递归处理左右子树，将返回的新子树根接回。必须先完成叶子判断，再修改孩子；否则子树剪枝形成的新叶子会被误认为原始叶子，导致级联删除。
必删区域中的节点没有任何合法方案可以保留，而算法保留了区域外的全部节点，所以所得树的保留节点数最大。已被整体删除的子树无需继续遍历。
解题步骤
- 在修改孩子之前检查当前节点是否是原始叶子的父亲；若是，整棵当前子树必须移除。
- 否则递归处理左右孩子并把结果接回。
- 按题目约定处理空树及单节点树。
代码实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
private boolean leaf(TreeNode node) {
return node != null && node.left == null && node.right == null;
}
public TreeNode prune(TreeNode root) {
if (root == null || leaf(root) || leaf(root.left) || leaf(root.right)) {
return null;
}
root.left = prune(root.left);
root.right = prune(root.right);
return root;
}
}
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func isLeaf(node *TreeNode) bool {
return node != nil && node.Left == nil && node.Right == nil
}
func prune(root *TreeNode) *TreeNode {
if root == nil || isLeaf(root) || isLeaf(root.Left) || isLeaf(root.Right) {
return nil
}
root.Left = prune(root.Left)
root.Right = prune(root.Right)
return root
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：递归空间 $O(h)$，n 为节点数、h 为树高。
关键点总结
[!green]
每个原始叶子的父节点都是必删点；直接剪去这些必删点覆盖的子树，保留其余节点，就是保留节点最多的方案。
易错点总结
[!yellow]
不能先递归更新孩子后再判断它们是不是叶子，否则会错误地级联删除整棵树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1325. 删除给定值的叶子节点 | 中等 | 原题会继续删除新产生的目标叶子，本题只依据原始叶子找父节点，剪枝条件与时机不同。 |
| 1110. 删点成林 | 中等 | 同样删除节点及重连树结构，原题保留被删节点下面的森林，本题直接移除指定父节点的整棵子树。 |