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
这道题让我们求二叉树的路径的和等于一个给定值，说明了这条路径不必要从根节点开始，可以是中间的任意一段，而且二叉树的节点值也是有正有负。那么可以用递归来做，相当于先序遍历二叉树，对于每一个节点都有记录了一条从根节点到当前节点到路径，同时用一个变量 curSum 记录路径节点总和，然后看 curSum 和 sum 是否相等，相等的话结果 res 加1，不等的话继续查看子路径和有没有满足题意的，做法就是每次去掉一个节点，看路径和是否等于给定值，注意最后必须留一个节点，不能全去掉了，因为如果全去掉了，路径之和为0，而如果给定值刚好为0的话就会有问题，整体来说不算一道很难的题，参见代码如下：
解法一：
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
int res = ;
vector<TreeNode*> out;
helper(root, sum, , out, res);
return res;
}
void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) {
if (!node) return;
curSum += node->val;
out.push_back(node);
if (curSum == sum) ++res;
int t = curSum;
for (int i = ; i < out.size() - ; ++i) {
t -= out[i]->val;
if (t == sum) ++res;
}
helper(node->left, sum, curSum, out, res);
helper(node->right, sum, curSum, out, res);
out.pop_back();
}
};
我们还可以对上面的方法进行一些优化，来去掉一些不必要的计算，可以用 HashMap 来建立路径之和跟其个数之间的映射，即路径之和为 curSum 的个数为 m[curSum]，这里需要将 m[0] 初始化为1，后面会讲解原因。在递归函数中，首先判空，若为空，直接返回0。然后就是 curSum 加上当前结点值。由于此时 curSum 可能已经大于了目标值 sum，所以用 curSum 减去 sum，并去 HashMap 中查找这个差值的映射值，若映射值大于0的化，说明存在结束点为当前结点且和为 sum 的路径，这就相当于累加和数组快速求某个区域和的原理。当 curSum 等于 sum 的时候，表明从根结点到当前结点正好是一条符合要求的路径，此时 res 应该大于0，这就是为啥要初始化 m[0] 为1的原因，举个例子来说吧，看下面这棵树：
/ /
假设 sum=3，当遍历根结点1时，curSum 为1，那么 curSum-sum=-2，映射值为0，然后建立映射 m[1]=1。此时遍历结点2，curSum 为3，那么 curSum-sum=0，由于 m[0] 初始化为1，所以 res=1，这是 make sense 的，因为存在和为3的路径。此时再遍历到第二个结点1，curSum 为4，那么 curSum-sum=1，由于之前建立了 m[1]=1 的映射，所以当前的 res 也为1，因为存在以第二个结点1为结尾且和为3的路径，那么递归返回到结点2时候，此时的 res 累加到了2，再返回根结点1时，res 就是2，最终就返回了2，那么可以看出递归函数的意义，某个结点的递归函数的返回值就是该结点上方或下方所有和为 sum 的路径总个数，参见代码如下：
解法二：
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
unordered_map<int, int> m;
m[] = ;
return helper(root, sum, , m);
}
int helper(TreeNode* node, int sum, int curSum, unordered_map<int, int>& m) {
if (!node) return ;
curSum += node->val;
int res = m[curSum - sum];
++m[curSum];
res += helper(node->left, sum, curSum, m) + helper(node->right, sum, curSum, m);
--m[curSum];
return res;
}
};
下面这种方法非常的简洁，用了两个递归函数，其中的一个 sumUp 递归函数是以当前结点为起点，和为 sum 的路径个数，采用了前序遍历，对于每个遍历到的节点进行处理，维护一个变量 pre 来记录之前路径之和，然后 cur 为 pre 加上当前节点值，如果 cur 等于 sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解，这是 sumUp 递归函数。而在 pathSum 函数中，我们对当前结点调用 sumUp 函数，加上对左右子结点调用 pathSum 递归函数，三者的返回值相加就是所求，参见代码如下：
解法三：
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if (!root) return ;
return sumUp(root, , sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
int sumUp(TreeNode* node, int pre, int& sum) {
if (!node) return ;
int cur = pre + node->val;
return (cur == sum) + sumUp(node->left, cur, sum) + sumUp(node->right, cur, sum);
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/437
类似题目：
参考资料：
https://leetcode.com/problems/path-sum-iii/
https://leetcode.com/problems/path-sum-iii/discuss/91889/Simple-Java-DFS
https://leetcode.com/problems/path-sum-iii/discuss/91878/17-ms-O(n)-java-Prefix-sum-method