1080.md

1080. Insufficient Nodes in Root to Leaf Paths

Solution 1 (time O(n), space O(n))

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sufficientSubset(self, root, limit):
        """
        :type root: TreeNode
        :type limit: int
        :rtype: TreeNode
        """
        def check(node, cur_sum, limit):
            if node is None:
                return False
            if node.left is None and node.right is None:
                return node.val + cur_sum >= limit
            left = check(node.left, cur_sum + node.val, limit)
            right = check(node.right, cur_sum + node.val, limit)
            if not left:
            if not left:
                node.left = None
            if not right:
                node.right = None
            return node.left or node.right
        
        res = check(root, 0, limit)
        return root if res else None