题目描述
思路解析
一句话答案：LeetCode 437 路径总和 III 的最优解是前缀和加哈希表的一趟 DFS：把根到当前节点的累加和记作前缀和 prefix，以当前节点结尾、和为 targetSum 的路径数，等于祖先链上前缀和 prefix - targetSum 出现的次数。用哈希表边走边查边登记、回溯时撤销，时间 O(n)、空间 O(n)。
这道题的路径和普通路径有什么不同
题目求树中和等于 targetSum 的路径条数，但这里的路径被重新定义了：方向只能向下（父到子）、必须连续，起点和终点却都任意——不必从根出发，也不必到叶子结束。另外节点值可以是负数，这意味着「和已经超了就提前剪枝」之类的想法不成立，也让同一条链上可能出现多段和相同的情况。
为什么暴力枚举起点是 O(n²)
直觉做法是双重递归：外层枚举每个节点作为路径起点，内层从这个起点向下累加、每凑够一次 targetSum 就计一条。每个节点会被它的所有祖先各扫一遍，链状树时总工作量是 1 加到 n，时间 O(n²)。慢的根源是重复累加：从根到某个深处节点的这段和，被沿途每个起点反反复复地重新算。
前缀和为什么能把树上路径变成一次查表
把「根到节点 X 的累加和」叫作 X 的前缀和 prefix(X)。同一条根链上，从祖先 A 的下一个节点走到当前节点 cur 的这段路径，和恰好等于 prefix(cur) - prefix(A)——两段根链相减，公共部分抵消。想让这段和等于 targetSum，等价于在 cur 的祖先里找前缀和等于 prefix(cur) - targetSum 的位置。
于是「向下枚举所有起点」被翻转成「向上数一次祖先」：用哈希表记录当前根链上每个前缀和出现的次数，走到 cur 时查一下 prefix - targetSum 出现过几次，就是以 cur 结尾的合法路径数。这正是数组版两数之和的查表思想，原封不动搬到了树的根链上。
哈希表为什么要预置 0 出现 1 次，回溯为什么必须撤销
表里要先放一条「前缀和 0 出现 1 次」，代表空前缀：当 prefix(cur) 本身就等于 targetSum 时，要找的是前缀和为 0 的祖先——对应从根一路走到 cur 的整段路径，不预置就会漏数这一整类。
更关键的是回溯撤销：递归离开一个节点时，必须把它的前缀和从表里减掉。因为差值公式只对同一条根链上的祖先成立，若左子树登记的前缀和残留在表里，右子树查表时会把跨分支的组合误当成路径，而题目要求路径必须连续。哈希表在任意时刻只保存根到当前节点这条链上的前缀和——这就是算法全程维持的不变量。
复杂度怎么算，容易错在哪
每个节点访问一次，查表、登记、撤销都是 O(1)，总时间 O(n)；哈希表加递归栈的空间是 O(n)。相比 O(n²) 的暴力，树一大差距悬殊。
三个高频坑：忘了预置空前缀，从根开始的路径全部漏掉；递归返回时不撤销登记，跨分支误判多算；以及哈希的值要存出现次数而不是存在与否——节点有负数时，同一个前缀和可能在一条链上出现多次，每一次都对应一条不同的路径。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
把「根到节点」的累加和叫前缀和。那么从祖先 A 的下一个节点走到当前节点，这段路径的和 = prefix(当前) − prefix(A)。想让它等于 8，就要找 prefix(A) = prefix(当前) − 8。于是：把沿途每个前缀和记进哈希，查 prefix−target 出现过几次，就有几条以当前结尾的合法路径。
准备 · 整棵树：先看清这棵树（含负数节点）。我们从根 5 出发做一趟 DFS，维护「根到当前」的前缀和，并把出现过的前缀和记进哈希表。哈希一开始放一个 {0: 1}——代表「空前缀」，专门用来命中那些从根直接开始的路径。
访问节点 5 · 前缀和 = 5：深度优先走到节点 5。把根到这里一路加起来，得到前缀和 = 5。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 5 − 8 = -3 的位置——中间那段的和就正好是 8。下一步去哈希表里查 -3 出现了几次。
节点 5 · 命中 0 → 累计路径 0：哈希里没有 -3，说明以节点 5 结尾没有和为 8 的路径，累计仍是 0。照例把当前前缀和 5 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 4 · 前缀和 = 9：深度优先走到节点 4。把根到这里一路加起来，得到前缀和 = 9。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 9 − 8 = 1 的位置——中间那段的和就正好是 8。下一步去哈希表里查 1 出现了几次。
节点 4 · 命中 0 → 累计路径 0：哈希里没有 1，说明以节点 4 结尾没有和为 8 的路径，累计仍是 0。照例把当前前缀和 9 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 3 · 前缀和 = 12：深度优先走到节点 3。把根到这里一路加起来，得到前缀和 = 12。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 12 − 8 = 4 的位置——中间那段的和就正好是 8。下一步去哈希表里查 4 出现了几次。
节点 3 · 命中 0 → 累计路径 0：哈希里没有 4，说明以节点 3 结尾没有和为 8 的路径，累计仍是 0。照例把当前前缀和 12 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 1 · 前缀和 = 13：深度优先走到节点 1。把根到这里一路加起来，得到前缀和 = 13。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 13 − 8 = 5 的位置——中间那段的和就正好是 8。下一步去哈希表里查 5 出现了几次。
节点 1 · 命中 1 → 累计路径 1：哈希里 5 出现了 1 次——意味着有 1 个祖先位置，从它的下一个节点走到当前正好凑出 8，于是路径数 += 1，累计变成 1。再把当前前缀和 13 记进哈希，供下面更深的子孙查询。
访问节点 2 · 前缀和 = 14：深度优先走到节点 2。把根到这里一路加起来，得到前缀和 = 14。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 14 − 8 = 6 的位置——中间那段的和就正好是 8。下一步去哈希表里查 6 出现了几次。
节点 2 · 命中 0 → 累计路径 1：哈希里没有 6，说明以节点 2 结尾没有和为 8 的路径，累计仍是 1。照例把当前前缀和 14 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 -1 · 前缀和 = 8：深度优先走到节点 -1。把根到这里一路加起来，得到前缀和 = 8。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 8 − 8 = 0 的位置——中间那段的和就正好是 8。下一步去哈希表里查 0 出现了几次。
节点 -1 · 命中 1 → 累计路径 2：哈希里 0 出现了 1 次——意味着有 1 个祖先位置，从它的下一个节点走到当前正好凑出 8，于是路径数 += 1，累计变成 2。（命中的是基底 0，代表「从根一路下来」这条路径本身就等于 target。）再把当前前缀和 8 记进哈希，供下面更深的子孙查询。
访问节点 3 · 前缀和 = 11：深度优先走到节点 3。把根到这里一路加起来，得到前缀和 = 11。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 11 − 8 = 3 的位置——中间那段的和就正好是 8。下一步去哈希表里查 3 出现了几次。
节点 3 · 命中 0 → 累计路径 2：哈希里没有 3，说明以节点 3 结尾没有和为 8 的路径，累计仍是 2。照例把当前前缀和 11 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 8 · 前缀和 = 13：深度优先走到节点 8。把根到这里一路加起来，得到前缀和 = 13。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 13 − 8 = 5 的位置——中间那段的和就正好是 8。下一步去哈希表里查 5 出现了几次。
节点 8 · 命中 1 → 累计路径 3：哈希里 5 出现了 1 次——意味着有 1 个祖先位置，从它的下一个节点走到当前正好凑出 8，于是路径数 += 1，累计变成 3。再把当前前缀和 13 记进哈希，供下面更深的子孙查询。
访问节点 6 · 前缀和 = 19：深度优先走到节点 6。把根到这里一路加起来，得到前缀和 = 19。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 19 − 8 = 11 的位置——中间那段的和就正好是 8。下一步去哈希表里查 11 出现了几次。
节点 6 · 命中 0 → 累计路径 3：哈希里没有 11，说明以节点 6 结尾没有和为 8 的路径，累计仍是 3。照例把当前前缀和 19 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 2 · 前缀和 = 15：深度优先走到节点 2。把根到这里一路加起来，得到前缀和 = 15。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 15 − 8 = 7 的位置——中间那段的和就正好是 8。下一步去哈希表里查 7 出现了几次。
节点 2 · 命中 0 → 累计路径 3：哈希里没有 7，说明以节点 2 结尾没有和为 8 的路径，累计仍是 3。照例把当前前缀和 15 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 7 · 前缀和 = 22：深度优先走到节点 7。把根到这里一路加起来，得到前缀和 = 22。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 22 − 8 = 14 的位置——中间那段的和就正好是 8。下一步去哈希表里查 14 出现了几次。
节点 7 · 命中 0 → 累计路径 3：哈希里没有 14，说明以节点 7 结尾没有和为 8 的路径，累计仍是 3。照例把当前前缀和 22 记进哈希（次数 +1），让更深的子孙能查到它。
访问节点 -2 · 前缀和 = 13：深度优先走到节点 -2。把根到这里一路加起来，得到前缀和 = 13。要数「以当前节点结尾、和为 8」的路径：等价于在祖先里找前缀和等于 13 − 8 = 5 的位置——中间那段的和就正好是 8。下一步去哈希表里查 5 出现了几次。
节点 -2 · 命中 1 → 累计路径 4：哈希里 5 出现了 1 次——意味着有 1 个祖先位置，从它的下一个节点走到当前正好凑出 8，于是路径数 += 1，累计变成 4。再把当前前缀和 13 记进哈希，供下面更深的子孙查询。
答案 · 路径数 = 4：一趟 DFS 走完，累计的路径数就是答案：和为 8 的向下路径共 4 条。每个节点只访问一次、哈希查/改都是 O(1)，所以整体时间 O(n)，远优于暴力的 O(n²)。
参考代码
class Solution { public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> cnt = new HashMap<>(); cnt.put(0L, 1); // 基底：空前缀出现 1 次 return dfs(root, 0L, targetSum, cnt); } private int dfs(TreeNode node, long prefix, int target, Map<Long, Integer> cnt) { if (node == null) return 0; prefix += node.val; // 根到当前的前缀和 int paths = cnt.getOrDefault(prefix - target, 0); // 命中=合法路径 cnt.merge(prefix, 1, Integer::sum); // 记入当前前缀 paths += dfs(node.left, prefix, target, cnt); paths += dfs(node.right, prefix, target, cnt); cnt.merge(prefix, -1, Integer::sum); // 回溯撤销 return paths; }}复杂度
- 时间：O(n)，每个节点访问一次，哈希查/改 O(1)
- 空间：O(n)，哈希表 + 递归栈，最坏（链状树）O(n)
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
打家劫舍 III
LeetCode 337 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题