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 = 0; vector<TreeNode*> out; helper(root, sum, 0, 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 = 0; i < out.size() - 1; ++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(); } };
我们还可以对上面的方法进行一些优化，来去掉一些不必要的计算，我们可以用哈希表来建立所有的前缀路径之和跟其个数之间的映射，然后看子路径之和有没有等于给定值的，参见代码如下：
解法二：
class Solution { public: int pathSum(TreeNode* root, int sum) { unordered_map<int, int> m; m[0] = 1; return helper(root, sum, 0, m); } int helper(TreeNode* node, int sum, int curSum, unordered_map<int, int>& m) { if (!node) return 0; 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; } };
下面这种方法非常的简洁，也是利用了前序遍历，对于每个遍历到的节点进行处理，维护一个变量pre来记录之前路径之和，然后cur为pre加上当前节点值，如果cur等于sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解，参见代码如下：
解法三：
class Solution { public: int pathSum(TreeNode* root, int sum) { if (!root) return 0; return sumUp(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } int sumUp(TreeNode* node, int pre, int& sum) { if (!node) return 0; int cur = pre + node->val; return (cur == sum) + sumUp(node->left, cur, sum) + sumUp(node->right, cur, sum); } };
本文转自博客园Grandyang的博客，原文链接：二叉树的路径和之三[LeetCode] Path Sum III ，如需转载请自行联系原博主。