删除给定值的叶子节点

难度: Medium

给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。

注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。

也就是说，你需要重复此过程直到不能继续删除。

示例 1：

输入：root = [1,2,3,2,null,2,4], target = 2
输出：[1,null,3,null,4]
解释：
上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。
有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。

示例 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]
解释：每一步都删除一个绿色的叶子节点（值为 2）。

示例 4：

输入：root = [1,1,1], target = 1
输出：[]

示例 5：

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

提示：

1 <= target <= 1000
每一棵树最多有 3000 个节点。
每一个节点值的范围是 [1, 1000] 。

Submission

运行时间: 23 ms

内存: 16.5 MB

# 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 not root:
            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

Explain

该题解采用递归的方式来解决问题。递归的基本思路是从树的叶子节点开始向上工作，检查每个节点是否应该删除。首先，递归调用自身来处理当前节点的左右子节点。一旦左右子树处理完成，检查当前节点是否为叶子节点（即没有左右子节点），并且节点的值等于target。如果是，则将该节点删除（即返回None）。如果不是，则返回当前节点。这个过程会一直递归地向上回溯至树的根节点，确保所有符合条件的叶子节点都被删除。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 not root:
            return None
        # 递归地删除左右子树中的目标叶子节点
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        # 检查当前节点是否是一个叶子节点，并且值等于target
        if root.val == target and not root.left and not root.right:
            return None
        # 如果当前节点不需要删除，返回当前节点
        return root

Explore

在递归处理时，每次从一个节点返回到其父节点前，都会重新检查该节点是否变成了叶子节点且其值是否等于目标值。这是通过递归函数在处理完一个节点的所有子节点后，再次检查该节点的状态实现的。如果一个节点的左右子节点都被递归调用返回了None（表示子节点为目标叶子节点并已被删除），那么这个节点在检查后如果也满足叶子节点且值等于目标值的条件，就会被删除。这样，即使一个节点在递归调用前不是叶子节点，但在其子节点被删除后变成了叶子节点，也会在递归回溯时被检查并可能被删除。

递归删除操作停止的条件是遇到了一个空节点（None），这表示已经到达了树的边界。在递归的每一层，函数首先检查当前节点是否为空，如果是，则立即返回None。这确保了递归总会在到达叶子节点后的下一层结束。因此，在任何正常的树结构中，递归都不会形成无限循环，因为每次调用都会向着树的叶子节点前进，最终到达树的底部并开始回溯。

在题解中，当一个叶子节点需要被删除时，递归函数返回None给其父节点。父节点会用这个None值来更新与被删除节点的关联（即更新父节点的左子节点或右子节点链接为None）。这样，被删除的节点就与其父节点断开了关联。这种处理方式简单且有效地利用了递归函数的返回值来管理树节点之间的连接关系。

在树的结构处理中，直接删除一个非叶子节点会导致其子节点失去父节点的链接，这可能会使整个子树丢失，除非额外处理这些子节点的重新连接。此外，题目的要求是删除值等于目标值的叶子节点。因此，即使非叶子节点的值等于target，也不能直接删除它，因为它还拥有子节点。只有当这些子节点被递归处理并删除后，该节点如果变成叶子节点且其值等于target，才能被删除。这保证了只删除符合条件的叶子节点，并保持树的完整性。