LC 112 & LC 113

Solution to LeetCode 112 Path Sum and LeetCode 113 Path Sum II.

LeetCode 112

Path Sum (Easy) [link]

1] Recursive solution. DFS.

Time complexity O(n). Space complexity 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def sumToTarget(root, targetSum):
            if not root.left and not root.right and targetSum == 0:
                return True
            if not root.left and not root.right:
                return False
            if root.left:
                targetSum -= root.left.val
                if sumToTarget(root.left, targetSum):
                    return True
                targetSum += root.left.val
            if root.right:
                targetSum -= root.right.val
                if sumToTarget(root.right, targetSum):
                    return True
                targetSum += root.right.val
            return False 

        if not root:
            return False
        return sumToTarget(root, targetSum - root.val)

2] Iterative solution. BFS using Stack.

Time complexity O(n). Space complexity 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        stack = []
        if not root: return False

        stack.append((root, root.val))
        while stack:
            cur_node, cur_val = stack.pop()
            if not cur_node.left and not cur_node.right and cur_val == targetSum:
                return True
            if cur_node.right:
                stack.append((cur_node.right, cur_node.right.val + cur_val))
            if cur_node.left:
                stack.append((cur_node.left, cur_node.left.val + cur_val))
        return False

LeetCode 113

Path Sum II (Easy) [link]

Iterative solution using Queue or Stack.

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        if not root:
            return res

        que = deque([(root, root.val, [root.val])])
        while que:
            # for i in range(len(que)):
            cur_node, cur_val, path = que.popleft()
            if not cur_node.left and not cur_node.right and cur_val == targetSum:
                res.append(path)

            if cur_node.left:
                que.append((cur_node.left, cur_node.left.val + cur_val, path+[cur_node.left.val]))
            if cur_node.right:
                que.append((cur_node.right, cur_node.right.val + cur_val, path+[cur_node.right.val]))
        return res

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        if not root:
            return res

        stack = [(root, root.val, [root.val])]
        while stack:
            # for i in range(len(que)):
            cur_node, cur_val, path = stack.pop()
            if not cur_node.left and not cur_node.right and cur_val == targetSum:
                res.append(path)
            if cur_node.right:
                stack.append((cur_node.right, cur_node.right.val + cur_val, path+[cur_node.right.val]))
            if cur_node.left:
                stack.append((cur_node.left, cur_node.left.val + cur_val, path+[cur_node.left.val]))
        return res