Hot 100 --- 路径总和 III

本文概览：本文以LeetCode题目"路径总和III"为例，讲解二叉树上的前缀和+哈希表方法，重点说明与数组版560题的区别——多路径导致需要回溯哈希表

一、题目

路径总和III题目

二、题目分析

题目要求：给定二叉树的根节点和一个整数 targetSum，求节点值之和等于 targetSum 的路径数目。路径不需要从根节点开始，也不需要在叶子节点结束，但必须从父节点到子节点往下走

这道题和力扣 560 题"和为 K 的子数组"是同一个思路——前缀和 + 哈希表。但二叉树比数组多了一个核心问题：路径有分支。数组是一条路走到底，而二叉树遍历完左子树要换到右子树，这个"换路"的过程就是回溯，哈希表必须跟着回溯，否则右子树会查到左子树的残留数据

思路概览

Java 实现代码如下

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> map = new HashMap<>();
    // 初始化
    map.put(0L, 1);
    return dfs(root, 0L, map, targetSum);
}

private int dfs(TreeNode node, long curSum, Map<Long, Integer> map, long targetSum) {
    // 递归出口
    if (node == null) {
        return 0;
    }
    // 当前节点的路径和
    curSum += node.val;
    // 查找符合条件的路径数量
    int count = map.getOrDefault(curSum - targetSum, 0);
    // 添加当前节点的路径和
    map.put(curSum, map.getOrDefault(curSum, 0) + 1);

    // 递归搜索左子树
    count += dfs(node.left, curSum, map, targetSum);
    count += dfs(node.right, curSum, map, targetSum);

    // 回溯
    map.put(curSum, map.get(curSum) - 1);
    return count;
}

思路简要说明

整体思路分三层：

前缀和：算出每个节点从根到自身的路径和 curSum。如果当前 curSum 减去之前某个节点的前缀和等于 targetSum，说明这两个节点之间的路径和就是 targetSum
哈希表加速：用哈希表记录遍历过的前缀和及出现次数，每到一个节点查 curSum - targetSum 在不在表里，O(1) 完成查找
回溯：二叉树有分支，遍历完一个节点的子树后，要把它的前缀和从哈希表中删掉（计数 -1），这样回到上层去走另一条分支时，哈希表里只保留当前路径上的前缀和

另外两个细节：哈希表 key 用 Long 防溢出；初始放入 (0L, 1) 处理"从根节点开始就满足条件"的情况

三、思路详解

第一步：前缀和的思路

先回忆前缀和解决"路径和等于目标值"的核心思想

假设从根到当前节点的路径和是 curSum，从根到之前某个祖先节点的路径和是 preSum。如果 curSum - preSum = targetSum，说明从那个祖先节点的下一个节点到当前节点的路径和，恰好等于 targetSum

根 → ... → 祖先节点 → ... → 当前节点

preSum = 根到祖先节点的和
curSum = 根到当前节点的和
curSum - preSum = 祖先节点之后到当前节点的和

如果 curSum - preSum == targetSum，就找到了一条符合条件的路径

所以每到一个节点，只需要查：之前有没有某个前缀和等于 curSum - targetSum？有几个？用哈希表记录前缀和出现的次数，查找就是 O(1)

第二步：从一条路径到多条路径

在数组（560 题）中，路径只有一条，从头到尾遍历一遍，哈希表只管往里加，不需要删

但二叉树是一棵树，从根往下走会有分叉。用 DFS 先序遍历时，走到左子树最深处后要"退回来"走右子树。这个"退回来"就是问题所在

看这棵树：

先序遍历的顺序是：10 → 5 → 3 → 2 → -3

遍历到 3 时，curSum = 18（10+5+3），哈希表里存了 {0, 10, 15}
遍历完 3 要去 2，此时 3 这条路走完了，3 的前缀和 18 必须清掉
同样，遍历完 5 的整个左子树（3、2 都走完了），要回到 10 去走右子树 -3 了，5 子树中的所有前缀和（15、18、17）都必须清掉

只要切换分支，就必须清理。因为哈希表里存的是"当前路径上经过的前缀和"，一旦离开这条路径，这些前缀和就不再属于当前路径了。如果不清掉，去 -3 那边查找时就会查到左子树残留的前缀和，这些数据和右子树毫无关系，会导致多算

解决方法就是回溯：遍历完一个节点的左右子树后，把它的前缀和从哈希表中删掉（计数 -1）。这样回到上层去走另一条分支时，哈希表里只有当前路径上的前缀和

第三步：为什么用先序遍历？

前缀和的核心是"从根节点一直往下累加"。只有先序遍历（根→左→右）才能保证：每到一个节点时，curSum 就是从根节点到当前节点的路径和

        10
       /  \
      5    -3

先序遍历：10 → 5 → -3
  curSum：  10 → 15 → 7
  每一步都是从根到当前节点的路径和 ✓

中序遍历：5 → 10 → -3
  curSum：  5 → 15 → 12
  第一步 5 不是从根到5的路径和（应该是15），前缀和意义失效 ✗

第四步：完整的执行过程

以这棵树为例，targetSum = 8：

      10
     /  \
    5    -3
   / \     \
  3   2     11
 / \   \
3  -2   1

满足条件的路径有三条：5→3（和8）、5→2→1（和8）、-3→11（和8）

下面逐步走一遍。核心要盯住哈希表的状态——它必须始终只反映"当前正在走的那条路径"上的前缀和。进入一个节点时把前缀和加进去，离开这个节点时把前缀和拿出来，哈希表就始终和当前路径同步

初始状态：哈希表 {0:1}（0 表示"还没开始走"的状态）

访问节点 10（当前路径：10）

curSum = 0 + 10 = 10
查 10 - 8 = 2 → 哈希表 {0:1} 中没有 2，没找到
把 10 加入哈希表 → {0:1, 10:1}
继续往左子树 5 走

访问节点 5（当前路径：10→5）

curSum = 10 + 5 = 15
查 15 - 8 = 7 → 哈希表 {0:1, 10:1} 中没有 7，没找到
把 15 加入哈希表 → {0:1, 10:1, 15:1}
继续往左子树 3 走

访问节点 3（当前路径：10→5→3）

curSum = 15 + 3 = 18
查 18 - 8 = 10 → 哈希表 {0:1, 10:1, 15:1} 中 10 出现 1 次！找到一条路径
- 这条路径是从前缀和为 10 的节点（即根节点 10）的下一个节点（5）到当前节点（3），也就是 5→3，和为 8 ✓
把 18 加入哈希表 → {0:1, 10:1, 15:1, 18:1}
继续往左子树 3 走

访问节点 3（当前路径：10→5→3→3）

curSum = 18 + 3 = 21
查 21 - 8 = 13 → 哈希表中没有 13，没找到
把 21 加入哈希表 → {0:1, 10:1, 15:1, 18:1, 21:1}
左右子树为空，此路走到底，回溯：把 21 从哈希表删掉 → {0:1, 10:1, 15:1, 18:1}

访问节点 -2（当前路径：10→5→3→-2）

curSum = 18 + (-2) = 16
查 16 - 8 = 8 → 哈希表中没有 8，没找到
把 16 加入哈希表 → {0:1, 10:1, 15:1, 18:1, 16:1}
左右子树为空，回溯：把 16 删掉 → {0:1, 10:1, 15:1, 18:1}

节点 3 的左右子树都走完了，回溯：把 18 删掉 → {0:1, 10:1, 15:1}

访问节点 2（当前路径：10→5→2）

curSum = 15 + 2 = 17
查 17 - 8 = 9 → 哈希表 {0:1, 10:1, 15:1} 中没有 9，没找到
把 17 加入哈希表 → {0:1, 10:1, 15:1, 17:1}
继续往右子树 1 走

访问节点 1（当前路径：10→5→2→1）

curSum = 17 + 1 = 18
查 18 - 8 = 10 → 哈希表中 10 出现 1 次！找到一条路径
- 从前缀和为 10 的节点（根节点 10）的下一个节点（5）到当前节点（1），也就是 5→2→1，和为 8 ✓
把 18 加入哈希表 → {0:1, 10:1, 15:1, 17:1, 18:1}
左右子树为空，回溯：把 18 删掉 → {0:1, 10:1, 15:1, 17:1}

节点 2 的子树走完，回溯：把 17 删掉 → {0:1, 10:1, 15:1}

节点 5 的子树全部走完，回溯：把 15 删掉 → {0:1, 10:1}

访问节点 -3（当前路径：10→-3）

curSum = 10 + (-3) = 7
查 7 - 8 = -1 → 哈希表 {0:1, 10:1} 中没有 -1，没找到
把 7 加入哈希表 → {0:1, 10:1, 7:1}
继续往右子树 11 走

访问节点 11（当前路径：10→-3→11）

curSum = 7 + 11 = 18
查 18 - 8 = 10 → 哈希表 {0:1, 10:1, 7:1} 中 10 出现 1 次！找到一条路径
- 从前缀和为 10 的节点（根节点 10）的下一个节点（-3）到当前节点（11），也就是 -3→11，和为 8 ✓
把 18 加入哈希表 → {0:1, 10:1, 7:1, 18:1}
左右子树为空，回溯：把 18 删掉 → {0:1, 10:1, 7:1}

节点 -3 的子树走完，回溯：把 7 删掉 → {0:1, 10:1}

节点 10 的子树全部走完，回溯：把 10 删掉 → {0:1}

最终结果：找到 3 条路径

1
2
3

5→3     和为 8 ✓
5→2→1   和为 8 ✓
-3→11   和为 8 ✓

第五步：哈希表的动态维护

回头看整个过程，哈希表的状态是动态变化的，它始终只反映当前正在走的那条路径：

走到节点 10→5→3 时，哈希表是 {0, 10, 15, 18}，这正是路径 10→5→3 上每个节点的前缀和
当从 3 回退到 5 去走 2 时，18 被删掉了，哈希表变成 {0, 10, 15}，对应路径 10→5
当从 5 回退到 10 去走 -3 时，15 也被删掉了，哈希表变成 {0, 10}，对应路径 10

进入节点就加，离开节点就删——这就是哈希表动态维护的规则。通过这个规则，哈希表始终和当前路径同步，查找时查到的永远是当前路径上的前缀和，不会混入其他分支的数据

这就是回溯的本质：不是回到上一个状态，而是把当前状态清理干净，让下一次查找在正确的路径上进行

第六步：两个关键细节

1. 为什么初始要放 (0L, 1)？

考虑这种情况：从根节点到某个节点的整条路径和恰好等于 targetSum

此时 curSum - targetSum = 0，需要在哈希表中查到 0。但 0 不是任何节点的路径和，它表示"还没开始走"的状态。如果不初始化 (0, 1)，这种情况就会漏掉

比如上面例子中，如果 targetSum = 18，路径 10→5→3 的和恰好是 18。此时 curSum = 18，查 18 - 18 = 0，哈希表中 0 出现 1 次，count 加 1。这就是初始化的作用

2. 为什么用 Long 不用 int？

节点值范围 -10^9 到 10^9，节点数最多 1000。前缀和最坏 1000 × 10^9 = 10^12，超出 int 范围（约 2×10^9），必须用 Long

和 560 题的对比

	560 题（数组）	路径总和 III（二叉树）
路径结构	一条线性路径	多条分支路径
遍历方式	从左到右一遍	先序遍历（DFS）
哈希表	只加不删	加完要删（回溯）
前缀和含义	从第0个到当前的累加	从根到当前节点的累加
核心区别	不需要回溯	必须回溯