## # 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
``````

Approach 1:

Approach 2: