437. 路径总和 III
一句话套路树上前缀和 + 哈希(Q560 的树版)
题目描述
给定一个二叉树的根节点 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
思路
时间
O(n)空间
O(n)思路
路径必须「向下」但起终点任意 -> 等价于树上任意一条根向链上的子段和,
于是套用 Q560
DFS 维护根到当前的前缀和 cur,查有多少祖先的前缀和 = cur-target。
回溯时必须 cnt[cur]--(离开这条分支要把状态还回去),这是树上前缀和的命门。
对比
双重 DFS(每个结点都当一次起点)是 O(n^2)。若结点值全为非负,可以在「向下累积和已超过 target」时剪枝;但本题允许 -1000 ≤ val ≤ 1000,往下走不保证和变大,所以必须一路探到底 —— 这才是它需要前缀和的原因。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)C++17 题解
namespace lc0437 {
class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> cnt;
cnt[0] = 1; // 空前缀:从根出发的路径
return dfs(root, 0, (long long)targetSum, cnt);
}
private:
static int dfs(TreeNode* n, long long cur, long long target,
unordered_map<long long, int>& cnt) {
if (!n) return 0;
cur += n->val;
int ans = cnt[cur - target]; // 以 n 为终点、起点是某祖先的路径条数
++cnt[cur];
ans += dfs(n->left, cur, target, cnt);
ans += dfs(n->right, cur, target, cnt);
--cnt[cur]; // 回溯!兄弟分支不该看到这条路径的前缀和
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0437::Solution s;
TreeNode* a = buildTree({10, 5, -3, 3, 2, nullopt, 11, 3, -2, nullopt, 1});
CHECK_EQ(s.pathSum(a, 8), 3); // 5->3, 5->2->1, -3->11
TreeNode* b = buildTree({5, 4, 8, 11, nullopt, 13, 4, 7, 2, nullopt, nullopt, nullopt, 1});
// 注意路径起点不必是根:5->4->11->2 与 4->11->7 都算,共 2 条
// (同一棵树用 Q112/113「根到叶」只会有 1 条,这就是两者的区别)
CHECK_EQ(s.pathSum(b, 22), 2);
CHECK_EQ(s.pathSum(nullptr, 0), 0);
freeTree(a);
freeTree(b);