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