删除给定值的叶子节点-LeetCode

1325. 删除给定值的叶子节点 - Delete Leaves With a Given Value

🎯 问题描述（来源于LeetCode）

描述：
给你一棵以 root 为根的二叉树和一个整数 target，请你删除所有值为 target 的叶子节点。
注意，删除一个叶子节点后，其父节点可能变成新的叶子节点。如果新叶子节点的值也等于 target，则应继续删除。
重复此过程直到无法继续删除，返回删除后的根节点。

说明：

• 叶子节点指没有子节点的节点。
• 删除操作会持续进行，直到没有值为 target 的叶子节点。

示例：

• 示例 1：

输入: root = [1,2,3,2,null,2,4], target = 2
输出: [1,null,3,null,4]
解释: 
- 删除值为2的叶子节点（原树中的左叶子2和右子树的叶子2）
- 父节点2变成叶子节点且值为2，继续删除
- 最终只剩1,3,4

• 示例 2：

输入: root = [1,3,3,3,2], target = 3
输出: [1,3,null,null,2]

• 示例 3：

输入: root = [1,2,null,2,null,2], target = 2
输出: [1]

💻 解题思路

思路1：后序遍历 + 递归删除

算法步骤

1. 递归终止条件：

   • 如果 root 为 None，直接返回 None。

2. 后序遍历处理子树：

   • 先递归删除左子树中满足条件的叶子节点：root.left = self.removeLeafNodes(root.left, target)
   • 再递归删除右子树中满足条件的叶子节点：root.right = self.removeLeafNodes(root.right, target)

3. 判断当前节点：

   • 经过上述处理后，当前节点的左右孩子已经是最新的状态（可能被删除或保留）。
   • 如果当前节点的值等于 target，且左右孩子均为 None（即当前节点已成为叶子节点），则返回 None 给父节点，表示删除该节点。
   • 否则，返回当前节点 root。

4. 重复删除：

   • 由于递归是自底向上的，当某个节点的子节点被删除后，该节点可能变成新的叶子节点，下一次递归返回时会再次检查，从而继续删除。

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if root.val == target and not root.left and not root.right:
            return None
        return root

思路1：📊 性能分析

• 时间复杂度：$O(n)$，每个节点恰好被访问一次。
• 空间复杂度：$O(h)$，递归调用栈的深度等于树的高度，最坏情况 $O(n)$。

思考

• 本题的核心是后序遍历：必须先处理子节点，才能判断父节点是否成为新的需要删除的叶子节点。
• 该递归方法天然支持“反复删除”的过程，因为子节点的删除会反映到父节点的左右指针上，父节点的判断会在同一次递归返回前执行。
• 也可以使用迭代 + 栈的后序遍历模拟，但递归写法最简洁。
• 注意：本题与 814. 二叉树剪枝 类似，但剪枝是根据子树是否包含 1（即是否含有目标值）来删除整个子树，而本题只删除值为 target 的叶子节点，且可能逐层向上删除。两者都利用后序遍历，但判断条件不同。