LeetCode 1325. 删除给定值的叶子节点
题目描述
题意分析
删除值等于
target的叶子节点，并继续删除由此新产生的目标叶子，直到不能再删。节点的值等于目标还不够，必须同时没有左右孩子；原本不是叶子的节点也可能在孩子删完后满足条件。
解法：后序遍历
核心思路
[!blue]
当前节点是否应该删除，取决于左右子树删除后的结果，所以要先处理孩子，再处理自己，也就是后序遍历。
把递归函数定义为：接收一棵子树，返回完成所有必要删除后的新根。若整棵子树被删空，就返回空。父节点必须把这个返回值写回原来的孩子位置，才能真正断开被删除的子树。
左右递归结束后，两个孩子都已经稳定。若当前节点的左右孩子均为空且值为
target，它就是应删除的叶子，返回空；否则保留当前节点并返回它。这样一趟遍历就能完成连锁删除：孩子删空会立刻反映在父节点的判断中。被保留的节点要么值不是目标，要么仍有已经处理完成的孩子，之后不会再变成可删除的目标叶子，因此不需要从根重复扫描。
解题步骤
- 当前节点为空时直接返回空，表示该位置没有需要保留的子树。
- 递归处理左右子树，分别用返回值更新
root.left和root.right。- 检查更新后的节点：两孩子都为空且节点值等于
target时返回空，否则返回root。- 整棵树也使用同一个返回约定，最外层返回值就是删除后的根。
根节点同样可能被删掉，无需单独寻找它的父节点。只有一个节点时，是否返回空完全由它的值是否等于
target决定。
代码实现
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(h)$，递归栈深度等于树高；树退化为链时为 $O(n)$。
关键点总结
[!green]
- 后序遍历先确定孩子的最终状态，再判断当前节点是否成为目标叶子。
- 返回值代表保留后的子树根，返回空就表示删除，父节点必须接回这个结果。
- 连锁删除沿同一次递归的回溯方向完成，每个节点无需反复检查。
易错点总结
[!yellow]
- 在处理孩子之前就完成判断，会漏掉孩子删除后新形成的目标叶子。
- 只判断节点值而不判断两个孩子是否为空，会连带删掉仍应保留的后代。
- 只递归调用而不更新孩子链接，父节点仍会指向已经返回空的旧节点。
- 调用者也要接住最外层返回值，否则无法得到根节点被删除后的空树。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 814. 二叉树剪枝 | 中等 | 同样后序剪枝，本题删除目标叶子后还可能产生新的目标叶子，原题删除不含1的整棵子树。 |
| 补充题 118. 二叉树的叶子父节点剪枝 | 中等 | 变形题只依据原始叶子找父节点并剪去子树，本题会继续处理新产生的目标叶子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！