path_sum_ii.py

from pathlib import Path
import sys

sys.path.append(str(Path(__file__).resolve().parent.parent))

from binary_tree import create_binary_tree


class Solution:
    def hasPathSum(self, root, targetSum):
        if root is None:
            return []

        result = []

        def backtrack(node, solution, curr_sum):
            if node is None:
                return

            solution.append(node.val)
            curr_sum += node.val

            if not node.left and not node.right and curr_sum == targetSum:
                result.append(solution[:])

            backtrack(node.left, solution, curr_sum)
            backtrack(node.right, solution, curr_sum)

            solution.pop()

        backtrack(root, [], 0)
        return result


if __name__ == "__main__":

    root = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]
    bt = create_binary_tree(root)

    solution = Solution()

    targetSum = 22
    result = solution.hasPathSum(bt, targetSum)
    assert result == [[5, 4, 11, 2], [5, 8, 4, 5]]
    print(result)
    print("Test Case 1 Passed!")