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:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
Code
1
2
3
4
5
6
|
public class {
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);
}
|
近期评论