[LeetCode] 113. Path Sum II

Problem : https://leetcode.com/problems/path-sum-ii/

Use backtracking approach to collect all valid paths.

# 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: TreeNode, targetSum: int) -> List[List[int]]:    
        def allPaths(node, tmp):
            tmp.append(node.val)
            
            if not node.left and not node.right:
                yield tmp[:]
            else:
                if node.left:
                    yield from allPaths(node.left, tmp)
                if node.right:
                    yield from allPaths(node.right, tmp)
            
            tmp.pop()
        
        return [path for path in allPaths(root, []) if sum(path) == targetSum] if root else []

An iterative solution based on 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: TreeNode, targetSum: int) -> List[List[int]]:
        if not root: return []
        result = []
        
        stack = [(root, [root.val])]
        
        while stack:
            node, path = stack.pop()
           
            if not node.left and not node.right:
                if sum(path) == targetSum:
                    result.append(path)
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
        
        return result

Edited on 04/22/2021. Update the DFS solution with 'yield' and 'yield from'.

Edited on 08/04/2021. Small refactor to the DFS solution.

Edited on 08/04/2021. Add the stack based iterative solution.