# 437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

# Solution

Approach 1: recursive -- find num of paths with root included, plus pathSums of the children. Time: T(N) = 2T(N/2) + O(N) --> Nlog(N), if tree balanced.

Approach 2: DFS -- along the way, we record all possible sums up until that node (the prefix sum). Time: NlogN if tree balanced (N nodes, each node logN lookup at the prefix sum).

Approach 3: a development on Approach 2 -- the prefix sums does't have to be a list; it's fine for it just be a dict/hashtable with {sum: frequence} to saves lookup time. Time: O(N) because we traverse each node once.

# Code (Python)

Approach 1:

    def pathSum(self, root, target):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        return self._path_sum_with_root(root, target) + self.pathSum(root.left, target) + self.pathSum(root.right, target)
    
    def _path_sum_with_root(self, root, target): # can be recursive too -- self._path_sum_with_root(root.left, target - root.left.val)
        if not root:
            return 0
        result = 0
        stack = [(root, root.val)]
        while stack:
            node, sum_so_far = stack.pop()
            if sum_so_far == target:
                result += 1
            if node.left:
                stack.append((node.left, node.left.val + sum_so_far))
            if node.right:
                stack.append((node.right, node.right.val + sum_so_far))
        return result

Approach 2:

    def pathSum(self, root, target):
        if not root:
            return 0
        num_sums = [0] # we need a container here because python passes by value. alternatively we could do self.num_sums
        self._path_sum(root, [root.val], target, num_sums)
        return num_sums[0]
    
    def _path_sum(self, node, current_sums, target, num_sums):
        num_sums[0] += sum(map(lambda val: val == target, current_sums))
        for child in (node.left, node.right):
            if not child:
                continue
            sum_length = len(current_sums)
            current_sums.append(0)
            current_sums = list(map(lambda val: val + child.val, current_sums))
            self._path_sum(child, current_sums, target, num_sums)
            current_sums = current_sums[:sum_length]
            current_sums = list(map(lambda val: val - child.val, current_sums))

Approach 3:

    def pathSum(self, root, target):
        if not root:
            return 0
        return self._helper(root, 0, target, {0:1})
    
    def _helper(self, node, current_sum, target, prefix_sums):
        if not node:
            return 0
        new_current_sum = node.val + current_sum
        result = prefix_sums.get(new_current_sum - target, 0)
        if new_current_sum not in prefix_sums:
            prefix_sums[new_current_sum] = 0
        prefix_sums[new_current_sum] += 1
        result += self._helper(node.left, new_current_sum, target, prefix_sums) + self._helper(node.right, new_current_sum, target, prefix_sums)
        prefix_sums[new_current_sum] -= 1
        return result

# Code (C++)

Approach 1:

Approach 2: