Leetcode 1157 Solution

This article provides solution to leetcode question 1157 (insufficient-nodes-in-root-to-leaf-paths)
Categories:
Tags:
Access this page by simply typing in "lcs 1157" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths

Solution

# 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]:
        dummy_root = TreeNode()
        dummy_root.left = root

        self.dfs(dummy_root, 0, limit)

        return dummy_root.left

    def dfs(self, root, pathsum, limit):
        left_max = 0
        left_none = root.left is None
        if root.left is not None:
            left_max = self.dfs(root.left, pathsum + root.left.val, limit)
            if pathsum + left_max < limit:
                root.left = None

        right_max = 0
        right_none = root.right is None
        if root.right is not None:
            right_max = self.dfs(root.right, pathsum + root.right.val, limit)
            if pathsum + right_max < limit:
                root.right = None

        if left_none:
            return root.val + right_max
        elif right_none:
            return root.val + left_max
        else:
            return root.val + max(left_max, right_max)