Path Sum III

437. 路径总和III

分析

使用前缀和优化路径求和
- 前缀和定义：到当前节点的路径和（包括当前节点）
- 公式：假设当前路径的前缀和为 cur，目标和为 targetSum，那么我们需要寻找路径的前缀和 cur - targetSum
  - 若前缀和 cur - targetSum 存在，说明存在一条路径满足路径和等于 targetSum
具体步骤
- 使用哈希表 count 存储前缀和及其出现的次数：
  - count[0] = 1 初始化，表示路径和为 0 的路径有 1 条（即从根节点开始时）
- 深度优先搜索（DFS）遍历树的每个节点，维护当前路径的前缀和：
  - 更新当前节点的前缀和 cur
  - 检查是否存在路径满足 cur - targetSum
  - 将当前路径的前缀和存入哈希表
  - 递归遍历左右子树
  - 回溯时，删除当前节点对前缀和的贡献（将 count[cur]--）

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(h)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution
{
public:
    std::unordered_map<long, int> count; // 哈希表存储前缀和及其出现次数
    int res = 0; // 记录满足条件的路径数

    int pathSum(TreeNode* root, int targetSum) {
        count[0] = 1; // 初始化路径和为 0 的路径有 1 条
        dfs(root, targetSum, 0); // 开始 DFS 遍历
        return res; // 返回结果
    }

    void dfs(TreeNode* root, int targetSum, long cur) {
        if (!root) return; // 如果当前节点为空，直接返回

        cur += root->val; // 更新当前路径和
        res += count[cur - targetSum]; // 检查是否存在前缀和满足条件
        count[cur]++; // 更新哈希表，记录当前路径和

        dfs(root->left, targetSum, cur); // 遍历左子树
        dfs(root->right, targetSum, cur); // 遍历右子树

        count[cur]--; // 回溯时移除当前节点对前缀和的贡献
    }
};