【LeetCode】437. Path Sum III

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

题解：

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

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

 1 class Solution {
 2 public:
 3     int pathSum(TreeNode* root, int sum) {
 4         unordered_map<int, int> 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<int, int>& 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 };