437 路径总和III

解题思路：
\qquad 这道题的诉求可以拆分成两部分：1 找到所有可能的路径；2 快速计算路径的和。
\qquad 由于题目要求路径方向是向下的，因而可以采用深度优先搜索（dfs） 的遍历方式，遍历所有的路径。
\qquad 对于这种累加和的问题，可以适用前缀和+Map的方式，进行快速计算。正常来说计算区间的前缀和需要遍历所有的元素累加，前缀和而是利用两个前缀和的差来计算。如果目标和targetSum是已知的，当前点的前缀和current是已知的，要找的区间开始节点的前缀和是可以计算 = current - targetSum，因而可以通过map快速查找。

	map<long long, int> m;

    int pathSum(TreeNode* root, int targetSum) {
       m[0] = 1;
       return searchTree(root, targetSum, 0);
    }
    
    int searchTree(TreeNode* root, int target, long long preSum)
    {
        int ans = 0;
        if(root == nullptr) return 0;
        preSum += root->val;
        if(m.count(preSum-target)) ans += m[preSum-target];
         m[preSum]++;
        ans += searchTree(root->left, target, preSum);
        ans += searchTree(root->right, target, preSum);
        m[preSum]--;
        return ans;
    }