Problem(root to any)

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

思路

1. because the path can start at any node, and end node should be under start node.

2. Therefore,

   1. path sum of root to any = path sum of the section of root.left to any

   2. path sum of the section of root.right to an

   3. path sum of starting from root to any node

3. path sum of starting from root to any node

   1. absolutely starts from root , which means the path includes root.

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int pathSumFrom(TreeNode root, int sum) {

        if (root == null) return res;
        if (sum == root.val) res++;
        res += pathSumFrom(root.left, sum - root.val);
        res += pathSumFrom(root.right, sum - root.val);

        return res;
    }

Optimization(prefix sum using map)

1. use a map to record the prefix from root to a certain node
   1. key: prefix sum
   2. value: how many ways get to this prefix sum
2. sum - (sum - target) = target
3. if map contains a key of sum - target, the ways to add to result

    private int result;
    public int pathSum(TreeNode root, int sum) {
        result = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        helper(root, sum, 0, map);
        return result;
    }

    private void helper(TreeNode root, int target, int sum, Map<Integer, Integer> map) {
        if (root == null) return;

        sum += root.val;

        if (map.containsKey(sum - target)) {
            result += map.get(sum - target);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);

        helper(root.left, target, sum, map);
        helper(root.right, target, sum, map);

        map.put(sum, map.get(sum) - 1);
    }