LeetCode #437 Path Sum III

Easy

Problem

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 — Recursion

Like #112, we should recursively find matched path from root. However, it’s different that we have to do pathSum for left and right subtrees as well. Besides, once there is matched path found, it shouldn’t stop so the rest path will be examined, too.

Complexity

If we assume counts of nodes in this tree is n, the recursion will run on n + (n/2)*2 + (n/4)*4 + … + 1*n nodes. Therefore, it’s time complexity is O(nlogn).

For space complexity, the maximum calls in calling stack will be h if h denotes to the length of the deepest path in this tree. Thus, it uses O(h) extra space. Or you can say O(logn) because h is bounded by logn.

Solution — Hash Map

If we observe recursive behavior in recursion approach, it will be found that we always start with one node and traverse all it’s possible path downward. Therefore, if we can save accumulative sum from the each root node to current node in a hash map, a matched path can be easily looked up by hash_map.get(acc_sum — sum).

For example, assume there is a path 5 -> -4 -> 6 -> -1 and sum = 2. Because all accumulative sums are all in the hash map, which means it will be {5: 1, 1: 1, 7: 1, 6: 1}, then acc_sum — sum = [5 + (-4) + 6] — 2 = 5 should be in the hash map, which also means that -4 -> 6 is a path whose sum is equal to sum = 2.

By the idea mentioned above, we can pick matched count in a bottom-up manner so this approach can be very performant.

Complexity

Because this approach will only visit each node once, it’s time complexity is O(n) if n denotes to counts of nodes in this tree.

However, it may need to record accumulative sum for each node so it uses O(n) extra space.