问题可以替换为，一个数组，求其有多少个子数组和为 target，两者方法是一样的。

对于数组，可以 hash 存储前缀和，若当前前缀和是 preSum，那么到此 index 为止，ans += sum[preSum - target]，这是很显然的。

对树上的，有一个树上前缀和，sum[i] 表示 i 到根节点的和，对于任意一条链 u, v，其和为 sum[u] + sum[v] - sum[lca(u, v)] - sum[father_lca(u, v)]

而题目要求的路径是向下的，就简单了。和数组一样的方式计算就行。

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        sum[0] = 1;       // 这一句话容易忽略
        return solve(root, targetSum, 0);
    }

private:
    unordered_map<int, int> sum;

    int solve(TreeNode *root, const int &targetSum, int preSum) {
        if(root == nullptr) return 0;
        int ret = 0;
        preSum += root -> val;
        if(sum.find(preSum - targetSum) != sum.end())
            ret += sum[preSum - targetSum];
        ++ sum[preSum];
        ret += solve(root -> left, targetSum, preSum);
        ret += solve(root -> right, targetSum, preSum);
        -- sum[preSum];
        return ret;
    }
};