根到叶路径上的不足节点

标签: 树 深度优先搜索 二叉树

难度: Medium

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。

叶子节点，就是没有子节点的节点。

示例 1：

输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]

示例 2：

输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3：

输入：root = [1,2,-3,-5,null,4,null], limit = -1
输出：[1,null,-3,4]

提示：

  • 树中节点数目在范围 [1, 5000] 内
  • -105 <= Node.val <= 105
  • -109 <= limit <= 109

Submission

运行时间: 41 ms

内存: 17.6 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 sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        #不是一个个删除，而是连续删除，示例三
        limit-=root.val
        if root.left is root.right:#叶子节点
            return None if limit>0 else root
        if root.left: root.left=self.sufficientSubset(root.left,limit)
        if root.right: root.right=self.sufficientSubset(root.right,limit)
        return root if root.left or root.right else None

Explain

这个题解使用了递归的方式处理每个节点，以判断是否保留或删除该节点。首先，每次递归调用都会从limit中减去当前节点的值，然后检查当前节点是否为叶子节点（即同时没有左右子节点）。对于叶子节点，如果剩余的limit值大于0，说明这条路径的总和不足，因此需要删除这个叶子节点。对于非叶子节点，递归地调用左右子节点，更新当前节点的左右子节点引用。最后，如果一个节点的左右子节点都被删除了，说明这个节点也变成了不足节点，因此也应该被删除。整个过程从根节点开始递归地处理，直到所有的不足节点都被删除。

时间复杂度: O(n)

空间复杂度: O(h)，其中h是树的高度。在最坏的情况下，这可以达到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 sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        # 更新limit为当前节点后的剩余值
        limit -= root.val
        # 检查当前节点是否为叶子节点
        if root.left is root.right:  # 即 if both are None
            # 如果是叶子节点且路径总和不足，返回None以删除该节点
            return None if limit > 0 else root
        # 递归检查左子节点
        if root.left: root.left = self.sufficientSubset(root.left, limit)
        # 递归检查右子节点
        if root.right: root.right = self.sufficientSubset(root.right, limit)
        # 如果当前节点的所有子节点都被删除了，也需要删除当前节点
        return root if root.left or root.right else None

Explore

在这个问题中，目的是确保从根节点到任何叶子节点的路径上的节点值之和至少达到一个给定的limit。因此，每次递归调用时减去当前节点的值是为了跟踪从根节点到当前节点的累积和。这样，当到达叶子节点时，我们可以直接通过检查剩余的limit（即目标值减去路径上已累计的和）是否大于0来判断该路径的总和是否不足。如果选择减去其他数值，则无法正确地跟踪并判断是否满足条件。

在这种情况下，当前节点不会被删除。根据题解的逻辑，只有当一个节点的所有子节点都被删除时，该节点才会被考虑删除。如果一个节点至少有一个子节点没有被删除，那么这个节点仍然保留在树中，因为它至少有一条从它到叶子节点的有效路径，即路径总和达到或超过了给定的limit。

如果根节点自身就是一个不足节点，这意味着从根节点到任何叶子节点的路径之和都不能满足给定的limit条件。在这种情况下，整个树都会被视为不足，因此根据题解的逻辑，返回的结果会是None，表示整棵树都被删除了。

递归调用的终结条件是当遇到叶子节点时（即节点同时没有左右子节点）。在这种情况下，会根据剩余的limit值来决定是否删除该叶子节点。关于栈溢出的可能性，虽然在极端不平衡的大树中递归深度可能非常高，但Python通常能够处理相对较深的递归调用。不过，对于特别大的数据或极端情况，确实存在栈溢出的风险，这时可以考虑使用迭代方法或增加递归调用的最大深度。