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   1Return 3. The paths that sum to 8 are:1.  5 -> 32.  5 -> 2 -> 13. -3 -> 11

题解：

　　此题类似于字符串或者数组的区间问题，区间和、乘积等。最直接的思想就是枚举所有可能区间。此题先遍历树，在遍历过程中对遍历节点枚举以其为始点的所有区间的和是否等于sum。

Solution 1

1 class Solution { 2 public: 3     int pathSum(TreeNode* root, int sum) { 4         if (!root) 5             return 0; 6         int res = 0; 7         stack
     
       st; 8         TreeNode* cur = root; 9         while (cur || !st.empty()) {10             if (cur) {11                 st.push(cur);12                 cur = cur->left;13             } else {14                 cur = st.top();15                 st.pop();16                 int num = 0;17                 dfs(cur, num, sum);18                 res += num;19                 cur = cur->right;20             }21         }22         return res;23     }24     void dfs(TreeNode* root, int& num, int sum) {25         if (!root)26             return;27         if (root->val == sum) {28             ++num;29         }30         dfs(root->left, num, sum - root->val);31         dfs(root->right, num, sum - root->val);32         33     }34 };
     

 

Solution 2

　　以root为根节点的树的sum = 以root为起点的区间满足条件的个数 + 以root左孩子为根节点的树的sum + 以root右孩子根节点的树的sum，得到递推关系。

　　注意 dfs 搜索的是以root为起点的区间，而pathSum搜索的是以root为根节点的树，pathSum没有要求区间必须以root为起点。

1 class Solution { 2 public: 3     int pathSum(TreeNode* root, int sum) { 4         if (!root) 5             return 0; 6         return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); 7     } 8     int dfs(TreeNode* root, int sum) { 9         int num = 0;10         if (!root)11             return 0;12         if (root->val == sum) {13             ++num;14         }15         num += dfs(root->left, sum - root->val);16         num += dfs(root->right, sum - root->val);17         return num;18     }19 };

 

Solution 3

　　思路用的是数组字符串区间常用的哈希存储思想，一般来讲树上不太常用，严格来讲应该和前缀和有些相似。

1 class Solution { 2 public: 3     int pathSum(TreeNode* root, int sum) { 4         unordered_map
     
       m; 5         m[0] = 1; 6         return helper(root, sum, 0, m); 7     } 8      9     int helper(TreeNode* node, int sum, int curSum, unordered_map
      
       & m) {10         if (!node) 11             return 0;12         curSum += node->val;13         int res = m[curSum - sum];14         ++m[curSum];15         res += helper(node->left, sum, curSum, m) + helper(node->right, sum, curSum, m);16         --m[curSum];17         return res;18     }19 };