C++ | Leetcode C++题解之第437题路径总和III
题目：
题解：
class Solution {
public:
unordered_map<long long, int> prefix;
int dfs(TreeNode *root, long long curr, int targetSum) {
if (!root) {
return 0;
}
int ret = 0;
curr += root->val;
if (prefix.count(curr - targetSum)) {
ret = prefix[curr - targetSum];
}
prefix[curr]++;
ret += dfs(root->left, curr, targetSum);
ret += dfs(root->right, curr, targetSum);
prefix[curr]--;
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
prefix[0] = 1;
return dfs(root, 0, targetSum);
}
};