題目： LeetCode - 437. Path Sum III

題目說明

給一個 Tree、一個整數 sum，求樹中有幾段子樹的路徑和為 sum。

解題思路

遍歷整棵樹，currSum 紀錄從 root 到當前節點的路徑和，由於 currSum - (currSum - target) = target，所以只要看前面有幾種路徑和的值為 currSum - target 就可以得到以當前節點為終點的子樹路徑和為 sum 的個數，將次數加上 count 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        int count = 0;
        ++_m[0];
        traverse(root, 0, sum, count);
        return count;
    }
private:
    unordered_map<int, int> _m;
    
    void traverse(TreeNode* root, int currSum, int target, int& count)
    {
        if(!root) return;
        currSum += root->val;
        count += _m[currSum - target]; // currSum - (currSum - target) = target
        ++_m[currSum];
        traverse(root->left, currSum, target, count);
        traverse(root->right, currSum, target, count);
        --_m[currSum];
    }
};