437.路径总和Ⅲ

题目：https://leetcode.cn/problems/path-sum-iii

思路

首先说明为何考虑使用前缀和思路。

先看二叉树的一条路径，也就是求这一条路径上，满足要求的数量——从根节点到该节点上路径和为 targetSum 的个数。于是开始思考，怎么求一个序列，从该节点开始等于 targetSum 的数量？用前缀和 + 哈希表。

注意的点

前缀和题目需要 umap[0] = 1。s 可以用全局变量来维护，也可以用参数传递。

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        
        unordered_map<long long, int> umap;
        umap[0] = 1;

        int ans = 0;
        auto dfs = [&](this auto&& dfs, TreeNode* node, long long s) -> void {
            if (node == nullptr) {
                return;
            }

            s += node->val;
            ans += umap[s - targetSum];

            umap[s]++;
            dfs(node->left, s);
            dfs(node->right, s);
            umap[s]--;

        };
        dfs(root, 0);
        return ans;
    }
};