题目描述

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

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

示例 1：

img

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

具体见题目描述。

算法思路

打眼一看其实这题真的唬人，因为本来树上搜索就比较麻烦，现在还不知道从哪个节点能找到这么一条路径，给人的第一念头就是想暴力，但是那肯定不会过的。但是仔细观察后就不难想到前缀和。大致这么个思路：我们记前缀和为presum，那么如上图那棵树而言，如果我们进行深搜，很容易发现第一次到达底部时,presum中的值为[10, 15, 18, 21]，那我们需要做什么呢？只需要找到presum[i], presum[j]使其满足presum[j] - presum[i] = targetnum即可，乍眼一看复杂度好像是个$O(n^2)$，但实则不然，我们可以这样想，对于每一个新加进来的前缀和prenum[k]，我们只需考虑prenum[k] - targetnum在前缀和出现了几次就可以了，仔细想想确实如此，那这样复杂度其实就是 $O(n)$。实在不理解的可以画一个流程图看看就明白了，只需要看一条路线即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    void dfs(TreeNode *root, int targetSum, long long last) {
        if (root == nullptr) {
            return;
        }
        
        last += root->val;
        // 查找是否存在满足条件的前缀和
        ans += presum[last - targetSum];  // 使用[]操作符，不存在时会返回0
        
        // 更新当前前缀和
        presum[last]++;
        
        // 递归处理左右子树
        dfs(root->left, targetSum, last);
        dfs(root->right, targetSum, last);
        
        // 回溯，移除当前路径的前缀和
        presum[last]--;
    }
    public:
        unordered_map<long long, long> presum;
        int ans;
        int pathSum(TreeNode* root, int targetSum) {
            presum[0] = 1; // 初始化，空路径的前缀和为0
            ans = 0;
            dfs(root, targetSum, 0);
            return ans;
        }
};

这里有个丢人的点就是我以前一直以为map.count(n)是返回n的数量，今天才知道他是返回0/1表示这个map中是否有这个键值……刷题的过程中可以弥补很多漏洞，加油吧！