题目描述
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:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
算法1
$O(n^2)$
如果可以从任意点开始,那么说明每个位置的node都有可能是start,那么只要这两种情况都过一遍就可以了。
在递归的时候用一个变量as_start
代表是否从当前节点开始。
时间复杂度分析:brute force相当于每个节点都尝试一遍,最坏情况是链表,每个位置要走$1 + 2 + … + (n - 1) + (n) = O(n^2)$次
C++ 代码
class Solution {
public:
int res;
int pathSum(TreeNode* root, int sum) {
traverse(root, sum, 0, true);
return res;
}
// there are two choice: 1 start from current node 2. keep going from current node
void traverse(TreeNode* root, int sum, int curr_sum, bool as_start) {
if (!root)
return;
curr_sum += root -> val;
if (curr_sum == sum)
res++;
traverse(root -> left, sum, curr_sum, false);
traverse(root -> right, sum, curr_sum, false);
if (as_start) {
traverse(root -> left, sum, 0, true); // start from next node, so sum is 0
traverse(root -> right, sum, 0, true);
}
}
};
算法2
$O(n)$ space $O(n)$
第一种复杂度高的原因是每个节点都要判断是否可以作为头节点,这样每个节点相当于都要再跑n次。
但是其实没有必要每次都查,这道题可以想像成two sum。
我们每次存当前到root的sum,这样每次到某个节点我们就只要看超过target的部分是不是已经在之前
存在过了(因为是root到当前节点的sum,所以必定是连续的)。
这个map我用m来表示,key是sum的值,value是个数,因为可能存在多个(假如有负数存在)。
two sum那道题其实也是类似的思想,只不过是有两个,所以不用map来存个数,直接用set来看存不存在
就可以了。
时间复杂度分析:每个节点只要走一次,但是要牺牲space来存之前的sum,所以space是n,time是n。
C++ 代码
class Solution {
public:
int res;
unordered_map<int, int> m;
int pathSum(TreeNode* root, int sum) {
if (!root)
return 0;
m[0] = 1; // the node before root: value is 0 and it has 1 way to get that sum
traverse(root, sum, root -> val);
return res;
}
void traverse(TreeNode* root, int sum, int curr_sum) {
if (!root)
return;
// check the complements
if (m.count(curr_sum - sum))
res += m[curr_sum - sum];
m[curr_sum]++;
if (root -> left)
traverse(root -> left, sum, curr_sum + root -> left -> val);
if (root -> right)
traverse(root -> right, sum, curr_sum + root -> right -> val);
m[curr_sum]--; // don't forget to set it back
}
};
这里算法一的时间复杂度不是 $O(2^n)$ 而应该是 $O(n^2)$,对于每个节点我们都以它为根遍历它的所有子路径,最坏情况下树为一条链,此时总复杂度为 $n + (n - 1) + (n - 2) +…+ 1 = O(n^2)$。
谢谢,已修改
有点像数组前缀和来求任意区间的和~
哈哈可以拓展到区间dp问题了