437. 路径总和III（Path Sum III）

频次 ★★★ · 难度 🟡 · 高频：字节/美团

题目

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

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

示例：

输入:        10
            /  \
           5   -3
          / \    \
         3   2    11
        / \   \
       3  -2   1
     targetSum = 8
输出: 3    （5→3、5→2→1、-3→11 三条）

思路

路径可以从任意节点开始，所以不能像 112. 路径总和 那样”从根往下减”。

关键是把它看成一维前缀和问题：从根到当前节点的路径就是一个数组，“以当前节点结尾、和为 target 的路径条数” = “有几个祖先前缀和等于 当前前缀和 - target”。这正是 560. 和为K的子数组 那一招，只是数组换成了根到节点的这条链。

于是用一个哈希表记录当前这条根到节点的链上每种前缀和出现了几次：

1. 进入节点：cur += node.val，先查 cur - target 在表里出现几次，累加到答案
2. 把 cur 记入表，递归左右子树
3. 离开节点：把 cur 从表里撤销 —— 表里只能存”当前这条链”，否则会把左子树的前缀和用到右子树上

prefix.put(0L, 1) 这个初始项代表空前缀，它负责统计那些恰好从根开始的路径。

代码

private int count = 0;
 
public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);                       // 空前缀:让「从根开始」的路径也能被统计到
    dfs(root, 0L, targetSum, prefix);
    return count;
}
 
private void dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
    if (node == null) return;
    cur += node.val;
    count += prefix.getOrDefault(cur - target, 0);   // 先查:有几个祖先前缀能凑出 target
    prefix.merge(cur, 1, Integer::sum);              // 再存:当前前缀入链
    dfs(node.left, cur, target, prefix);
    dfs(node.right, cur, target, prefix);
    prefix.merge(cur, -1, Integer::sum);             // 回溯:离开本节点必须撤销
}

朴素解法是双递归 O(n²)：对每个节点都以它为起点向下扫一遍。写起来简单，n ≤ 1000 时能过，但面试官通常会追问到前缀和这一版。

复杂度

• 时间：O(n) —— 每个节点进出各一次，哈希操作 O(1)
• 空间：O(n) —— 哈希表最多存一条链的前缀 + 递归栈 O(height)，最坏退化成链表时都是 O(n)

（双递归解法：时间 O(n²)，最坏 O(n²)；空间 O(height)）

边界条件

• 空树：直接返回 0
• targetSum = 0：查表在插入当前前缀之前，所以不会把”长度为 0 的路径”算进去
• 节点值为负 / 路径和为负：前缀和可能反复回到同一个值，哈希表计数天然支持
• 单条链退化成链表：递归深度 O(n)，注意栈溢出风险

变式

• 560. 和为 K 的子数组：同一招的一维原型，把树换成数组就不需要回溯撤销
• 112. 路径总和 / 113. 路径总和 II：路径必须根到叶，用”往下减”即可，不需要哈希表
• 路径可以拐弯（经过某节点向上再向下）：那就不是前缀和了，退化成 124. 二叉树中的最大路径和 那种后序返回值设计

易错点

• 必须用 long 存前缀和：节点值可到 ±10⁹、路径长可到 1000，int 会溢出（这是本题最常见的 WA）
• 回溯撤销不能省：prefix.merge(cur, -1, ...) 漏了，右子树会用到左子树的前缀，结果偏大
• 查表要在插入当前前缀之前：先插后查会把”当前节点自己构成的空路径”多算一次
• prefix.put(0L, 1) 忘了写，从根开始的整段路径统计不到
• 路径是单向向下的，别按”任意两点间路径”去想

面试追问

• 为什么 112 能”往下减”，437 不能？ 112 的路径起点固定是根，一路减到叶子判断是否为 0 即可；437 的起点任意，等价于”数组里找所有和为 target 的子段”，这类问题的标准解就是前缀和 + 哈希计数。
• 为什么哈希表要撤销，而 560 不用？ 560 的前缀是一条线性推进的序列，不会回退；树上 DFS 走完左子树要退回父节点换右子树，表里必须只保留”当前根到节点这一条链”的前缀，所以进出成对。
• 双递归 O(n²) 能过吗？ 本题数据量能过，但要主动说出”这是 O(n²)，前缀和可以做到 O(n)“，否则会被认为没看出问题本质。
• 如果要返回路径本身而不是数量？ 哈希表只存计数就不够了，得存”前缀和 → 该前缀结束的节点列表”，或者退回 O(n²) 的双递归边走边记路径。

关联题

• 同套路：560. 和为 K 的子数组 —— 前缀和 + 哈希计数的一维原型
• 同套路：113. 路径总和 II —— 起点固定的简化版
• 进阶：124. 二叉树中的最大路径和 —— 路径可拐弯时的后序返回值设计
• 知识点：树上 DFS 与回溯撤销见二叉树；前缀和配哈希的通用套路见哈希表