Paths with Sum: You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count 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).
Hints: #6, #14, #52, #68, #77, #87, #94, #103, #108, #115
解法1
暴力解决：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int countPathWithSum(Node node, int sum) {
if (node == null) {
return 0;
}
int countFromRoot = countPathWithSumFromNode(node, sum);
int countLeft = countPathWithSum(node.left, sum);
int countRight = countPathWithSum(node.right, sum);
return countFromRoot + countLeft + countRight;
}
private int countPathWithSumFromNode(Node node, int sum) {
if (node == null) {
return 0;
}
int count = 0;
if (sum == 0) {
count++;
}
count += countPathWithSumFromNode(node.left, sum - this.data);
count += countPathWithSumFromNode(node.right, sum - this.data);
return count;
}
|
两种办法来计算时间复杂度：
思路一，如果现在位于深度为d的节点，那么意味着前面已经走了d步（看countPathWithSumFromNode）。在一棵平衡的树里，最大深度d = logN（N=节点数），然后我们对多少个节点做了这件事情呢（看countPathWithSum），答案是N。那么就是说总的调用次数不会超过 d * N = N * logN。
思路二：当在root的时候，我们遍历了N - 1次（看countPathWithSum里对countPathWithSumFromNode的调用），在第二层的时候，我们遍历了 N - 3 次，。。。。，所以：
1
2
|
调用次数 = (N - 1) + (N - 3) + (N - 7) + (N - 15) + ... + (N - N)
root 第2层 第3层 第4层 第d层
|
那么有几个子式子呢？在一颗平衡的树里就是深度d个，d = logN，所以
1
|
调用次数 = logN * N - (1 + 3 + 7 + 15 + ... + N)
|
后面的1、3、7、15其实就等于 21- 1、22 - 1、23 - 1、24 - 1、…，忽略掉后面的-1，它们的和等于：
2 * (2d - 1) / (2 - 1) = 2 * 2d - 2 = 2 * N - 2，见等比数列求和公式
所以：
1
2
|
调用次数 = logN * N - 2 * N + 2
= logN * N
|
相关问题
先看类似的问题：给你一个数组，里面数字有正数负数，给一个数字targetSum，让你求出有多少个子串能够累加值等于targetSum。
1
2
3
|
index: 0 1 2 3 4 5 6 7 8
value: 10 -> 5 -> 1 -> 2 -> -1 -> -1 -> 7 -> 1 -> 2
runningSum: 10 15 16 18 17 16 23 24 26
|
如果 targetSum = 8，我们从index=0开始逐一往后，每次都是向前看，是否有子串能够sum == 8。比如我们现在已经跑到index=8了，那么有多少个子串sum == 8 呢？我们可以把 24 - 8 =16 看前面有多少个16。你可以发现array[2] == 16、array[5] == 16 ，这意味着什么呢？这意味着 array[3 ~ 8]和array[6 ~ 8]的和等于8。你可以看看是不是这样？
所以有了下面这个图解：
1
2
3
4
5
6
7
8
|
|<- runningSumY ->|
|<- runningSumX ->|<- targetSum ->|
|-----------------|---------------|
s x y
s: 起点下标
x: y之前的某个下标
y: 当前下标
|
所以这个问题就演变成为：我们找当前下标y前面的，有多少个x，能够使得[x + 1 到 y]之间的和等于targetSum。因为runningSumY和targetSum是已知的，所以就变成找有多少个runningSumX == runningSumY - targetSum。
那么我们就可以用一个Map来记录runningSum出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public int countTargetSum(int[] array, int targetSum) {
Map<Integer, Integer> runningSumMap = new HashMap<>();
int runningSum = 0;
int count = 0;
for (int i = 0; i < array.length; i++) {
runningSum += array[i];
// 增加runningSum的计数
increment(runningSumMap, runningSum);
// 如果当前runningSum就等于targetSum，那么它必定是一个合格的子串
if (runningSum == targetSum) {
count++;
}
int sum = runningSum - targetSum;
// 看前面的runningSumX出现了几次
count += runningSumMap.getOrDefault(sum, 0);
}
return count;
}
private void increment(Map<Integer, Integer> runningSumMap, int runningSum) {
int count = runningSumMap.getOrDefault(runningSum, 0);
count++;
runningSumMap.put(runningSum, count);
}
|
解法2
从上面的这个数组的问题可以获得灵感：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
public int countPathsWithSum(Node node, int targetSum, int runningSum, Map<Integer, Integer> runningSumMap) {
if (node == null) {
return 0;
}
int pathCount = 0;
runningSum += node.data;
if (targetSum == runningSum) {
pathCount++;
}
int sum = runningSum - targetSum;
pathCount += runningSumMap.getOrDefault(sum, 0);
increment(runningSumMap, runningSum);
pathCount += countPathsWithSum(node.left, targetSum, runningSum, runningSumMap);
pathCount += countPathsWithSum(node.right, targetSum, runningSum, runningSumMap);
// runningSumMap只能记录从根到当前节点的各种runningSum出现的次数
// 本调用返回后就回到了上一级，那么就要清除掉当前runningSum的计数
// 因为上一级只能看到更上级的runningSum计数
decrement(runningSumMap, runningSum);
return pathCount;
}
private void increment(Map<Integer, Integer> runningSumMap, int runningSum) {
int count = runningSumMap.getOrDefault(runningSum, 0);
count++;
runningSumMap.put(runningSum, count);
}
private void decrement(Map<Integer, Integer> runningSumMap, int runningSum) {
int count = runningSumMap.getOrDefault(runningSum);
count--;
if (count == 0) {
runningSumMap.remove(runningSum);
} else {
runningSumMap.put(runningSum, count);
}
}
|
时间复杂度：O(n)
空间复杂度：最高的空间复杂度是O(logN)，就是深度
评论