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

Analysis:

Use a map to store all sum results starting from root(origin root: 10) to any point before current node.

When we are at current node, first we calculate the path sum including current node -- curSum

delta = curSum - sum(the target), and see if delta exist in the map keys. If it exist, we increment total by map.get(delta)

because along the way, we might have multiple pathSums reaches the same total sum, so we increment by map.get(delta) but not just 1.

At the end of each recursion, we remove the curSum from map (decrement by 1 if more than 1) and carry on.

Complexity:

Time: O(n)

Space: O(logn) - despite recursion stack space, in the map, we only store logn element which is the height of the tree.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int total = 0;
    public int pathSum(TreeNode root, int sum) {
        if(root == null)
        {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        traverse(root, 0, sum, map);
        return total;

    }

    private void traverse(TreeNode root, int prevSum, int sum, Map<Integer,Integer> map)
    {
        if(root == null)
        {
            return;
        }
        int curSum = prevSum + root.val;
        int delta = curSum - sum;
        if(map.containsKey(delta))
        {
            total += map.get(delta);
        }
        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        traverse(root.left, curSum, sum, map);
        traverse(root.right, curSum, sum, map);
        map.put(curSum, map.get(curSum) - 1);
    }
}