437. 路径总和 III
3 min
题目
解法：前缀和映射
思路
前缀和 + 哈希表 + 深度优先搜索。通过记录根节点到当前节点的前缀和，利用哈希表快速查找满足条件的路径数量。
正确性基于前缀和思想：对于任意节点，从根到该节点的路径和为 curSum，若存在之前节点的前缀和为 curSum - targetSum，则这两个节点之间的路径和必为 targetSum。哈希表记录了所有祖先节点的前缀和出现次数，确保不遗漏任何可能的路径。回溯机制保证不同分支间状态隔离。
- Step 1: 初始化哈希表 prefix[0] = 1，表示空路径的前缀和
- Step 2: DFS 遍历每个节点，累加当前路径和 curSum
- Step 3: 查询哈希表中 curSum - targetSum 的出现次数，累加到答案
- Step 4: 将当前 curSum 加入哈希表，递归处理左右子树
- Step 5: 回溯时减少当前 curSum 的计数，恢复状态
复杂度
- 时间复杂度: ，每个节点仅访问一次，哈希表操作平均 。
- 空间复杂度: ，最坏情况下哈希表存储 个不同前缀和，递归栈空间 。
代码
class Solution {
public:
unordered_map<long long,int> prefix;
int ans = 0;
void dfs(TreeNode* node,long long curSum,int target){
if(!node) return;
curSum += node->val;
// 查找是否存在路径
if(prefix.count(curSum-target))
ans += prefix[curSum-target];
// 记录当前前缀
prefix[curSum]++;
dfs(node->left,curSum,target);
dfs(node->right,curSum,target);
// 回溯
prefix[curSum]--;
}
int pathSum(TreeNode* root,int targetSum){
class Solution {
public:
unordered_map<long long,int> prefix;
int ans = 0;
void dfs(TreeNode* node,long long curSum,int target){
if(!node) return;
curSum += node->val;
// 查找是否存在路径
if(prefix.count(curSum-target))
ans += prefix[curSum-target];
// 记录当前前缀
prefix[curSum]++;
dfs(node->left,curSum,target);
dfs(node->right,curSum,target);
// 回溯
prefix[curSum]--;
}
int pathSum(TreeNode* root,int targetSum){
prefix[0] = 1; // 空路径
dfs(root,0,targetSum);
return ans;
}
};