437. 路径总和 III

题目链接（中等）

题目描述

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

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

数据范围：

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

示例

示例 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

核心思路

路径不要求从根开始，也不要求在叶子结束，只要求方向向下（从父到子）。

两种解法：

1. 双重 DFS：以每个节点为起点，向下搜索路径和为 targetSum 的路径数目，把所有起点的结果加起来；
2. 前缀和 + 哈希表：把树上路径问题转成「数组上找子数组和为 targetSum」的问题，一次 DFS 搞定。

---

方法一：双重 DFS（暴力枚举起点）

思路及解法

第一步：定义 rootSum(node, target) 表示「以 node 为起点，向下延伸，路径和为 target 的路径数目」。

递归逻辑：

• 若 node 为空，返回 0；
• 若 node.val == target，计数 +1（路径就是 node 自己）；
• 递归左子树：rootSum(node.left, target - node.val)；
• 递归右子树：rootSum(node.right, target - node.val)；
• 返回三者之和。

第二步：对每个节点 node，调用 rootSum(node, targetSum)，把所有结果相加。

逻辑：外层枚举路径的起点，内层枚举从该起点向下的路径。

缺点：每个节点都要重新遍历它的子树，存在大量重复计算。

代码

class Solution:
    def pathSum(self, root: TreeNode | None, targetSum: int) -> int:
        def root_sum(node: TreeNode | None, target: int) -> int:
            """以 node 为起点，向下路径和为 target 的路径数"""
            if not node:
                return 0

            count = 0
            if node.val == target:
                count += 1

            count += root_sum(node.left, target - node.val)
            count += root_sum(node.right, target - node.val)
            return count

        if not root:
            return 0

        return (
            root_sum(root, targetSum)
            + self.pathSum(root.left, targetSum)
            + self.pathSum(root.right, targetSum)
        )

复杂度分析

• 时间复杂度：$O(n^2)$，对每个节点 node 求 rootSum 需要遍历它的子树 $O(n)$，共 $n$ 个节点。
• 空间复杂度：$O(n)$，递归栈深度最坏为 $n$。

---

方法二：前缀和 + 哈希表（推荐）

思路及解法

关键观察：把树上路径问题转成「数组上找子数组和为 targetSum」的问题。

前缀和定义：从根节点到当前节点的路径上所有节点的和，记为 curr。

核心等式：若从根到节点 A 的前缀和为 curr1，从根到节点 B（B 是 A 的后代）的前缀和为 curr2，则从 A 的子节点到 B 的路径和为 curr2 - curr1。

转化为：在 DFS 过程中，我们要找的是「以当前节点为终点，向下路径和为 targetSum」的路径数，等价于：

$$\text{存在某个祖先节点 } A，\text{使得 } curr - prefix[A] = targetSum$$

即：

$$prefix[A] = curr - targetSum$$

所以，用哈希表记录「从根到当前路径上，每个前缀和出现的次数」，遍历到节点时：

1. 计算当前前缀和 curr += node.val；
2. 在哈希表中查找 curr - targetSum 出现的次数，累加到答案；
3. 把当前 curr 加入哈希表；
4. 递归左右子树；
5. 回溯：把 curr 从哈希表中减 1（离开当前节点）。

初始化：prefix[0] = 1，表示「空路径」的前缀和为 0，这样能处理「路径从根节点开始」的情况。

代码

from collections import defaultdict

class Solution:
    def pathSum(self, root: TreeNode | None, targetSum: int) -> int:
        prefix = defaultdict(int)
        prefix[0] = 1     # 空路径的前缀和为 0

        def dfs(node: TreeNode | None, curr: int) -> int:
            if not node:
                return 0

            curr += node.val
            count = prefix[curr - targetSum]     # 查找匹配的前缀和
            prefix[curr] += 1                    # 记录当前前缀和
            count += dfs(node.left, curr)
            count += dfs(node.right, curr)
            prefix[curr] -= 1                    # 回溯

            return count

        return dfs(root, 0)

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(n)$，哈希表存储路径上的前缀和，递归栈深度最坏为 $n$。

---

两种方法对比

方法	时间	空间	特点
双重 DFS	$O(n^2)$	$O(n)$	思路直观，容易理解
前缀和 + 哈希	$O(n)$	$O(n)$	效率最优，需要理解前缀和转化

推荐：

• 面试开场：先讲双重 DFS，思路自然，容易理解；
• 追问优化：再讲前缀和，展示对「树上路径和 → 前缀和」转化的理解。

---

关键细节

1. 为什么双重 DFS 复杂度是 $O(n^2)$

外层遍历 $n$ 个节点，每个节点 node 都要遍历它的子树求 rootSum。最坏情况下（链状树），根节点的子树大小为 $n$，下一层为 $n-1$，…，总复杂度约 $O(n^2)$。

2. 前缀和的直觉

在数组上，「子数组和等于 target」等价于「两个前缀和之差等于 target」。在树上，同样的逻辑成立：

• 「从祖先 A 的子节点到当前节点 B 的路径和等于 target」
• 等价于「A 处的前缀和 = B 处的前缀和 - target」。

3. 为什么 prefix[0] = 1

表示「从根节点到当前节点」这条路径本身。如果没有这一项，就无法统计「从根开始」的路径。

举例：root = [10], targetSum = 10

• 若 prefix[0] = 1，dfs(root, 0)：
  • curr = 10，prefix[10 - 10] = prefix[0] = 1，count = 1；
• 若没有 prefix[0] = 1，则 prefix[10 - 10] = prefix[0] = 0，漏掉答案。

4. 为什么需要回溯（prefix[curr] -= 1）

因为哈希表中保存的应该是「当前路径上的前缀和」，而不是整棵树所有的前缀和。

回溯到父节点时，当前节点的前缀和不再属于新路径，必须从哈希表中移除，否则会统计到不在同一路径上的前缀和。

对比数组：数组上滑动窗口的 remove 也是类似逻辑。

5. 节点值可以为负数

因为节点值可以是负数，所以前缀和不一定单调递增，不能用双指针或单调栈，必须用哈希表。

6. defaultdict(int) 的便利

prefix[curr - targetSum] 在 key 不存在时返回 0，不需要提前判断。如果用普通 dict，需要写成 prefix.get(curr - targetSum, 0)。

---

总结

• 问题本质：树上「路径和等于 targetSum」的路径数量，路径方向向下；
• 双重 DFS：
  • 枚举每个节点作为起点；
  • 对每个起点向下 DFS 找路径和；
  • 时间 $O(n^2)$；
• 前缀和 + 哈希表：
  • prefix[curr] 记录从根到当前路径上，前缀和为 curr 的次数；
  • 用 prefix[curr - targetSum] 统计匹配路径；
  • DFS 结束时回溯（prefix[curr] -= 1）；
  • 时间 $O(n)$、空间 $O(n)$；
• 通用套路：「树上路径和」→「前缀和 + 哈希表」，与 LC 560「和为 K 的子数组」思路完全一致。

相关题目

• LC 560. 和为 K 的子数组（数组版前缀和）
• LC 112. 路径总和（路径必须从根到叶子）
• LC 113. 路径总和 II（求所有路径）
• LC 124. 二叉树中的最大路径和（树形 DP）