[LeetCode] Problem 437 - Path Sum III

Posted on | In ,

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

1
2
3
4
5
6
7
      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

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// “当前节点值” + “某一中间路径和” = “目标值”
// “当前节点累加的根路径和” = “之前某一节点中累加的根路径和” + “某一中间路径和” + “当前节点值”
// 可得“当前节点累加的根路径和” - “之前某一节点中累加的根路径和” = “目标值”
private int count = 0;

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

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

    currentSum += root.val;
    count += map.getOrDefault(currentSum - target, 0);

    map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
    traverse(root.left, map, target, currentSum);
    traverse(root.right, map, target, currentSum);
    map.put(currentSum, map.get(currentSum) - 1);
}