testing

pathsum.py

# https://leetcode.com/problems/path-sum-iii/

# Given a binary tree and a number ‘S’, find all paths in the tree such that the
# sum of all the node values of each path equals ‘S’. Please note that the paths
# can start or end at any node but all paths must follow direction from parent to
# child (top to bottom).

#            1
#            /\
#            7 9
#           /\  /\
#          5  6 2 3
# Given the binary tree our algorithm will have the following paths
# []
# [1]
# [1, 7] x
# [1, 7, 6] x
# [1, 7, 5] ok
# [1, 9] x
# [1, 9, 2] ok
# [1, 9, 3] x
def num_of_paths(root: Node, target: int) -> int:

    def helper(root: Node, path: [int]) -> int:
        if not root:
            return 0

        path.append(root.val)

        sum = 0
        occurence = 0
        for val in reversed(path):
            sum += val
            if sum == target:
                occurence++

        # how to not have the paths cloned?
        return = occurence + helper(root.left, path.clone()) + helper(root.right, path.clone())

    return helper(root, [])