No.437 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

• 二叉树的节点个数的范围是 [0,1000]
• -109 <= Node.val <= 109 
• -1000 <= targetSum <= 1000 

思路分析

不难看出本题一定会遍历到每个节点。而且方式一定是dfs。因为只有dfs我们才比较方便对路径进行处理。
常规的思路一定是存一下本节点之前遍历到的路径的所有值。并且回溯删除来保证只关注遍历到的节点所处的环境。

但是这样会比较复杂，如果只存之前遍历到的所有值，我们还得判断哪些区间可以加起来等于target。这样就是$O(n^2)$。

所以我们尝试用前缀和来简化一下，也就是在数组中存之前遍历到的所有从根节点开始的路径总和。
若一条路径上的节点为[1,2,3,4] 我们用前缀和存储变成[1,3,6,10] 当我们遍历到值为4的节点的时候，此时从根节点到本节点的路径总和是10，假设target是7，我们只需要找出来在前缀和数组中 值等于10-7也就是3的节点即可算作有效方案，此时复杂度为$O(n)$，因为需要对前缀和数组进行一次遍历。

本方案还可以进一步优化，因为我们要在数组里查找，而且是指定值去查找，就可以用哈希表来优化一下，最终查找的操作复杂度被我们从$O(n^2)$降低到了$O(1)$。

C++代码

class Solution {
public:
    int res = 0, tar;
    unordered_map<int, int> v;
    void dfs(TreeNode * root, int cur) {
        if (!root) return;
        int tmp = cur + root->val;
        res += v[tmp - tar];
        v[tmp]++; 
        dfs(root->left, tmp);
        dfs(root->right, tmp);
        v[tmp]--; // 回溯删除
    }
    int pathSum(TreeNode* root, int targetSum) {
        tar = targetSum;
        v[0] = 1;
        dfs(root, 0);
        return res;
    }
};