路径总和 III
Path Sum III
统计二叉树中节点值之和等于 targetSum 的路径数量；路径只能向下，起点和终点任意。
在力扣中练习题目描述
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 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
提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
解题思路
前缀和 + 回溯
把“路径和”变成两个前缀和之差
路径可以从任意节点开始，不能只用“从根出发的和”。把根到当前节点的和记作 cur，如果路径从某个祖先之后开始，那么这段路径的和就是 cur - prefix。
要让路径和等于 target，只需要 prefix = cur - target。用一个哈希表记录当前根到节点路径上各个前缀和出现的次数，进入节点时查表，就能一次得到“以当前节点结尾”的合法路径数。
关键在于哈希表必须随递归回溯：离开一个节点时，把它对应的前缀和减掉，否则兄弟分支的前缀会互相污染。
进入 7，当前前缀和 19；cur-target=11 在表中出现 1 次，新增 1 条路径。
命中意味着存在一条路径，结束于当前节点、和为 8。
- cur
- 19
- need
- 11
- total
- 2
自拟树中有负数，路径 1+7 和 3+5 都不从根开始；前缀相减正好把它们识别出来。时间 O(n)，哈希表最多保存 O(h) 个前缀。
易错点
- 忘记回溯：兄弟子树的路径会被错误计入。
- 没有初始化 prefix[0]：从根开始的路径全部漏掉。
- 用 int 存前缀和：节点值较大时可能溢出，应用 long long。
- 把路径理解成只能从根开始：会漏掉题目中大量合法路径。
双层递归 · 枚举起点
以每个节点为起点，向下累加找 target
逻辑最直白，但每个节点都向下扫一遍，最坏 O(n²)；仅作对照。
外层递归枚举路径起点：对每个节点，调用 countFrom 从它出发向下累加，统计有多少次累加和等于 target。
内层只走子树，因此路径一定向下；外层再把左右子树的答案加起来。正确性很直接，但同一个节点会被不同起点反复访问。
链状树上退化为 O(n²)。如果数据规模不大，这个版本足够；大规模输入应使用前缀和版本。
- 1以当前节点为起点，向下累加统计。
- 2递归统计左子树内部。
- 3递归统计右子树内部。
- 4三者相加。
易错点
- 内层也向父节点走：路径不再单向。
- 只统计从根开始的路径：漏掉起点在中间的路径。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [8,3,-2,1,5,null,9,null,7,4,6]，targetSum = 8空前缀和 0 先记 1 次；这样从根开始的路径也能用 cur - target = 0 命中。
查看 C++ 代码
延伸阅读
- “子数组和等于 k”与“树上路径和等于 k”共享同一个前缀和思路，只是树需要回溯。
- 路径只能向下时，前缀和表只保存当前根路径；如果是任意两点路径，问题会完全不同。