LeetCode 1325. 删除给定值的叶子节点
目录
题目描述
题意分析
给一棵二叉树和一个目标值
target，要求删掉所有值等于target的叶子节点。关键在于删除会传染：一个节点原本有孩子所以不是叶子，孩子被删光之后它自己就变成了叶子，如果它的值也等于target，同样要被删掉，而且要一直这样连锁下去直到没有节点可删。从这个描述能读出两个信号。一是判定条件依赖「删除之后的状态」而不是原始状态，所以任何自顶向下、只看一次的做法都会漏；二是删除操作会改变树的结构，需要有办法把「这棵子树没了」这个事实告诉父节点。
边界上最容易忽略的是根节点：如果整棵树最后只剩下根，而根的值恰好是
target，那么根也要被删掉，函数需要返回空树。所以返回类型必须是节点而不是void。
解法：后序遍历
核心思路
删除条件取决于孩子删除后的状态：孩子被删光后，父节点可能新变成值为
target的叶子。因此要用后序遍历，先处理左右子树，再判断当前节点。定义递归契约：
removeLeafNodes(node, target)返回“以node为根的子树完成所有连锁删除后的新根”；整棵子树被删空时返回null。父节点把递归结果写回left、right，拿到的就是两个孩子的最终状态。此时若当前节点左右孩子都为空且值等于
target，返回null；否则返回当前节点。一次回溯就能完成多层连锁删除，无需反复扫描整棵树。正确性说明：对任意子树做归纳。空树显然处理正确；假设左右子树的递归结果都正确，那么写回后，当前节点的两个孩子正是删除完成后的结果。算法随后严格按题意删除“此刻值为
target的叶子”，或保留当前节点，因此当前子树的返回结果也正确。由归纳可知根节点返回的就是最终答案。
解题步骤
- 遇到空节点，返回
null。- 递归处理左、右子树，并将返回的新根分别写回
root.left、root.right。- 回溯到当前节点时，检查它是否已经成为叶子且
root.val == target；若是，返回null表示删除整棵当前子树。- 否则返回
root，表示当前节点继续作为这棵子树的根。连锁删除示例：
root = [1,2,null,2]、target = 2。最底层的 2 先返回null；上一层 2 写回孩子后也变成目标叶子，继续返回null；根 1 的左指针最终被置空。每一层都只判断一次，但回溯顺序已经完成了重复删除。
代码实现
class Solution {
public TreeNode removeLeafNodes(TreeNode root, int target) {
if (root == null) {
return null;
}
root.left = removeLeafNodes(root.left, target);
root.right = removeLeafNodes(root.right, target);
if (root.left == null && root.right == null && root.val == target) {
return null;
}
return root;
}
}
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
if root == nil {
return nil
}
root.Left = removeLeafNodes(root.Left, target)
root.Right = removeLeafNodes(root.Right, target)
if root.Left == nil && root.Right == nil && root.Val == target {
return nil
}
return root
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点只进入和退出递归一次，节点上的判断与指针修改都是 $O(1)$。
- 空间复杂度：$O(h)$。
h是树高，空间来自递归栈；平衡树为 $O(\log n)$，退化链为 $O(n)$。
关键点总结
- 父节点依赖孩子的最终状态，遍历顺序必须是“左、右、根”的后序。
- 递归返回“处理后的子树根”，既能表达保留，也能用
null表达删除；根节点无需额外特判。- 必须把递归结果写回左右指针，否则下层删除不会反映到树结构中。
- 一轮后序遍历等价于题目要求的“不断删除直到稳定”：新产生的目标叶子会在同一次回溯中继续被删除。
易错点总结
- 先判断再递归：看到的是原始叶子状态。
[1,2,null,2]中上层 2 初次检查时还有孩子，之后不会再被检查，连锁删除失败。- 忘记写回递归结果：只调用递归却不执行
root.left = ...，下层即使返回null，原指针仍然存在。- 只判断节点值：
[2,3]、target = 2中根 2 不是叶子，不能连同非目标孩子一起删除。- 遗漏根节点删除：
[2]、target = 2的正确结果是空树，因此入口必须接收并返回递归得到的新根。- 反复整树扫描：结果虽正确，但目标值链会每轮只删一层，最坏退化为 $O(n^2)$；一次后序遍历即可完成。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 后序返回值只用于统计，不改动树的结构 |
| 814. 二叉树剪枝 | 中等 | 剪枝条件换成「子树中不含 1」，同一套返回新根范式 |
| 1120. 子树的最大平均值 | 中等 | 后序需要向上带回和与数量两个聚合量 |