路径总和 III | 秋招知识库

如果二叉树是一条链，本题就和 560. 和为 K 的子数组完全一样了：统计有多少个非空连续子数组的元素和恰好等于 $targetSum$ 。所以你必须先弄明白 560 题（特殊情况），再来做本题（一般情况）。560 题的做法见我的题解。

这两题的联系如下：

560. 和为 K 的子数组	437. 路径总和 III
连续子数组	方向向下的路径
前缀	从根节点开始的路径
做法：枚举子数组右端点，统计有多少个左端点	做法：枚举路径的终点，统计有多少个起点

我们要解决的问题是：DFS 遍历这棵树，遍历到节点 $node$ 时，假设 $node$ 是路径的终点，那么有多少个起点，满足起点到终点 $node$ 的路径总和恰好等于 $targetSum$ ？

和 560 题一样的套路：一边遍历二叉树，一边用哈希表 $cnt$ 统计前缀和（从根节点开始的路径和）的出现次数。设从根到终点 $node$ 的路径和为 $s$ ，那么起点的个数就是 $cnt [s - targetSum]$ ，加入答案。对比 560 题，我们在枚举子数组的右端点（终点），统计有多少个左端点（起点），做法完全一致。

答疑

问：为什么这样做是对的？不会漏算多算吗？

答：不会漏算多算。首先最暴力的做法是，枚举终点，枚举起点，判断起点到终点的路径和是否恰好等于 $targetSum$ ，是就把答案加一。暴力做法必然不会漏算多算。我们的做法其实是对暴力的优化，保留了枚举终点这一步，把枚举起点这一步通过哈希表优化成了 $O (1)$ 。

问：为什么要初始化哈希表 $cnt [0] = 1$ ？

答：同 560 题，这里的 $0$ 相当于前缀和数组中的 $s [0] = 0$ 。举个最简单的例子，根节点值为 $1$ ， $targetSum = 1$ 。如果不把 $0$ 加到哈希表中，按照我们的算法，没法算出这里有 $1$ 条符合要求的路径。也可以这样理解，要想把任意路径和都表示成两个前缀和的差，必须添加一个 $0$ ，否则当路径是前缀时（从根节点开始的路径），没法减去一个数，具体见前缀和及其扩展中的讲解。

问：为什么代码中要先更新 $ans$ ，再更新 $cnt$ ？

答：在 $targetSum \neq 0$ 的情况下，这俩谁先谁后都可以。但如果 $targetSum = 0$ ，假设根节点值为 $1$ ，如果先把 $cnt [1]$ 增加 $1$ ，再把 $ans$ 增加 $cnt [s - targetSum] = cnt [1] = 1$ ，就相当于我们找到了一条和为 $targetSum = 0$ 的路径，但和为 $0$ 的路径是不存在的。另一种理解方式是，空路径的元素和等于 $0$ ，我们把这个 $0$ 当作了符合要求的路径，但题目要统计的是非空路径。

问：代码中的「恢复现场」用意何在？

答：举个例子，递归完 $node$ 子树，如果接下来要递归 $node$ 父节点的右子树，我们不恢复现场，那么 $cnt$ 中还保存着 $node$ 子树的数据。但对于 $node$ 父节点的右子树来说，要计算的路径并不涉及到 $node$ 子树的任何节点。如果不恢复现场， $cnt$ 中统计的前缀和个数会更多，我们算出来的答案可能比正确答案更大。

问：为什么递归参数 $s$ 不需要恢复现场？

答： $s$ 是基本类型，在函数调用的时候会复制一份往下传递，s += node.val 修改的仅仅是当前递归函数中的 $s$ 参数，并不会影响到其他递归函数中的 $s$ 。注：如果把 $s$ 声明在递归函数外，全局只有一个 $s$ ，那么执行 s += node.val 就会影响全局了，这种情况需要写 s -= node.val 恢复现场。

问：能不能枚举起点？

答：首先对比一下，枚举终点的话，起点都在上面，都在一条链中（根到当前节点），很好维护；而枚举起点，终点都在下面（ $node$ 子树），是分散的，不好维护。对比可以发现，枚举终点，维护起点是更方便的。硬要枚举起点是可以做的，对于每个节点 $node$ ，返回根到 $node$ 子树中的每个节点的前缀和（返回一个哈希表）。在合并左右子树的哈希表时，应当使用启发式合并，也就是把小的哈希表合并到大的哈希表中，从而保证 $O (n \log n)$ 的时间复杂度。所以枚举起点不仅麻烦，而且更慢。

Python 解法1C++ 解法1

python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # key：从根到 node 的节点值之和
        # value：节点值之和的出现次数
        # 注意在递归过程中，哈希表只保存根到 node 的路径的前缀的节点值之和
        cnt = defaultdict(int)  
        cnt[0] = 1
        ans = 0

        # s 表示从根到 node 的父节点的节点值之和（node 的节点值尚未计入）
        def dfs(node: Optional[TreeNode], s: int) -> None:
            if node is None:
                return

            nonlocal ans
            s += node.val
            # 把 node 当作路径的终点，统计有多少个起点
            ans += cnt[s - targetSum]

            cnt[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)
            cnt[s] -= 1  # 恢复现场（撤销 cnt[s] += 1）

        dfs(root, 0)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        // key：从根到 node 的节点值之和
        // value：节点值之和的出现次数
        // 注意在递归过程中，哈希表只保存根到 node 的路径的前缀的节点值之和
        unordered_map<long long, int> cnt = {{0, 1}};
        int ans = 0;

        // lambda 递归
        // s 表示从根到 node 的父节点的节点值之和（node 的节点值尚未计入）
        auto dfs = [&](this auto&& dfs, TreeNode* node, long long s) {
            if (node == nullptr) {
                return;
            }

            s += node->val;
            // 把 node 当作路径的终点，统计有多少个起点
            ans += cnt[s - targetSum]; // 注意这样写会把 s-targetSum 插入哈希表，介意的话可以特判

            cnt[s]++;
            dfs(node->left, s);
            dfs(node->right, s);
            cnt[s]--; // 恢复现场（撤销 cnt[s]++）
        };

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

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (n)$ 。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

答疑 ​

复杂度分析 ​

分类题单 ​

答疑

复杂度分析

分类题单