路径总和 III

给定一个二叉树的根节点 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]
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000

解法一（枚举起点 + 深度优先搜索）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr)
        {
            return 0;
        }

        return countFrom(root, targetSum)
            + pathSum(root->left, targetSum)
            + pathSum(root->right, targetSum);
    }

private:
    int countFrom(TreeNode* node, long long targetSum) {
        if (node == nullptr)
        {
            return 0;
        }

        int ans = 0;
        if (node->val == targetSum)
        {
            ++ans;
        }

        ans += countFrom(node->left, targetSum - node->val);
        ans += countFrom(node->right, targetSum - node->val);

        return ans;
    }
};

解法二（前缀和 + 哈希表）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<long long, int> prefixCount;
    int ans = 0;

public:
    int pathSum(TreeNode* root, int targetSum) {
        prefixCount.clear();
        prefixCount[0] = 1;
        ans = 0;

        dfs(root, 0, targetSum);
        return ans;
    }

private:
    void dfs(TreeNode* node, long long prefix, long long targetSum) {
        if (node == nullptr)
        {
            return;
        }

        prefix += node->val;

        if (prefixCount.find(prefix - targetSum) != prefixCount.end())
        {
            ans += prefixCount[prefix 、argetSum];
        }

        prefixCount[prefix]++;

        dfs(node->left, prefix, targetSum);
        dfs(node->right, prefix, targetSum);

        prefixCount[prefix]--;
    }
};

核心思想

这题要求统计所有满足条件的向下路径。

路径可以从任意节点开始，也可以在任意节点结束，所以不能只从根节点开始查找，也不能只检查叶子节点。

最直接的做法是把每个节点都当作路径起点，再向下 DFS，统计从这个节点开始的路径。

这种做法容易理解，但在树退化成链时，会重复遍历大量节点，最坏时间复杂度为 O(n^2)。

更高效的做法是使用前缀和。

沿着从根节点到当前节点的路径定义前缀和：

prefix = 从根节点到当前节点的所有节点值之和

如果某条从祖先之后开始、到当前节点结束的路径和为 targetSum，那么：

当前前缀和 - 祖先前缀和 = targetSum

移项得到：

祖先前缀和 = 当前前缀和 - targetSum

所以遍历到当前节点时，只要知道当前路径上之前出现过多少次 prefix - targetSum，就能知道有多少条路径以当前节点结尾，并且路径和等于 targetSum。

这题最关键的观察是：

对于当前节点，合法路径的数量等于当前前缀和减去 targetSum 后，在当前根到父节点路径上出现的次数。

解法一：枚举起点

对于每个节点，都调用一次 countFrom。

countFrom(node, targetSum) 表示：

统计所有从 node 出发、沿向下方向延伸，并且路径和等于 targetSum 的路径

对当前节点有三种处理：

1. 如果当前节点值等于剩余目标值，找到一条路径。
2. 继续在左子树中寻找，剩余目标值减去当前节点值。
3. 继续在右子树中寻找，剩余目标值减去当前节点值。

而 pathSum(root, targetSum) 负责枚举每一个可能的起点：

countFrom(root, targetSum)
+ pathSum(root->left, targetSum)
+ pathSum(root->right, targetSum)

这种方法直接对应题意，但不同起点的 DFS 可能重复访问同一批节点。

解法二：前缀和 + 哈希表

前缀和解法只进行一次 DFS。

递归函数：

dfs(node, prefix, targetSum)

表示：

在从根节点到 node 的当前路径上，处理 node 及其子树

进入当前节点后，先更新前缀和：

prefix += node->val

然后查找：

prefix - targetSum

如果这个前缀和之前出现过 count 次，说明存在 count 条路径满足：

当前路径和 - 之前路径和 = targetSum

因此：

ans += prefixCount[prefix - targetSum];

之后把当前前缀和加入哈希表：

prefixCount[prefix]++;

再递归处理左右子树。

左右子树处理完成后，当前节点的前缀和不能继续影响其他分支，所以要回溯删除：

prefixCount[prefix]--;

哈希表存什么

代码使用：

unordered_map<long long, int> prefixCount;

其中：

• 键：某个前缀和
• 值：这个前缀和在当前根到父节点路径上出现的次数

例如：

prefixCount[x] = 3;

表示当前 DFS 路径上，已经有 3 个祖先位置的前缀和等于 x。

这些不同位置都可以作为路径的起点前一个位置，所以必须记录次数，而不能只记录是否出现过。

公式推导

设当前节点对应的前缀和为 prefix。

设某个祖先位置的前缀和为 previousPrefix。

从该祖先的下一个节点到当前节点的路径和为：

prefix - previousPrefix

题目要求路径和为 targetSum，所以：

prefix - previousPrefix = targetSum

移项得到：

previousPrefix = prefix - targetSum

因此，当前节点结尾的合法路径数量就是：

prefixCount[prefix - targetSum]

这就是代码查询的依据。

为什么要初始化 prefixCount[0] = 1

prefixCount[0] = 1 表示：

在根节点之前存在一个前缀和为 0 的位置。

它用于统计从根节点开始的路径。

例如只有一个节点：

root = [5]
targetSum = 5

访问节点 5 后：

prefix = 5

需要查找：

prefix - targetSum = 5 - 5 = 0

如果提前记录了 prefixCount[0] = 1，就能统计到从根节点开始的路径 [5]。

如果不初始化，就会漏掉所有从根节点开始的合法路径。

为什么必须回溯删除前缀和

哈希表只应该记录当前 DFS 路径上的前缀和。

处理完一个节点的整棵子树后，就要执行：

prefixCount[prefix]--;

否则这个前缀和会错误地保留到兄弟子树中。

例如：

    1
   / \
  2   3

处理完左子树后，如果不删除左分支产生的前缀和，右子树就可能错误地把左分支的前缀当成自己的祖先前缀。

但一条合法路径只能沿着父节点到子节点向下，不能从左子树跨到右子树。

所以回溯删除是保证路径方向和范围正确的关键。

为什么必须使用 long long

节点值范围为：

-10^9 <= Node.val <= 10^9

树中最多有 1000 个节点，因此一条路径的和可能达到 10^12 量级。

这个数值可能超出 int 的范围。

所以前缀和、目标前缀和以及哈希表的键都使用 long long：

unordered_map<long long, int> prefixCount;

虽然 targetSum 本身是 int，但参与减法时会转换为 long long，这样计算不会溢出。

边界情况

如果二叉树为空：

root = []

没有任何路径，返回 0。

如果目标值为 0，仍然可以统计路径和为 0 的路径。节点值允许为负数，因此不能使用只适用于正数的滑动窗口。

如果节点值为负数，前缀和可能减少，但前缀和公式仍然成立，不影响算法。

如果存在多个相同前缀和，哈希表记录出现次数，可以正确统计由不同起点形成的多条路径。

如果路径从根节点开始，prefixCount[0] = 1 可以正确统计。

如果路径在非叶子节点结束，只要当前前缀和满足条件，访问到当前节点时就会被统计，不要求继续走到叶子节点。

正确性证明

我们证明：前缀和 + 哈希表解法返回的 ans 正好是二叉树中所有和为 targetSum 的向下路径数量。

结论 1：DFS 过程中，哈希表只记录当前根到当前节点路径上的前缀和

开始 DFS 前，哈希表中只有：

prefixCount[0] = 1;

它表示根节点之前的虚拟位置。

访问一个节点时，算法先计算包含当前节点的前缀和，并把它加入哈希表。

然后递归处理左右子树。

左右子树处理完成后，算法删除当前节点对应的前缀和。

因此，在处理任意节点时，哈希表中记录的正好是从根节点到当前节点路径上、当前节点之前的所有前缀和。

结论 2：算法统计到的每条路径都满足路径和为 targetSum

处理当前节点时，当前前缀和为 prefix。

如果哈希表中存在一个前缀和：

previousPrefix = prefix - targetSum

那么从 previousPrefix 对应位置的下一个节点到当前节点的路径和为：

prefix - previousPrefix

代入得到：

prefix - (prefix - targetSum) = targetSum

由结论 1 可知，previousPrefix 对应的位置位于当前节点的祖先路径上。

所以形成的路径一定是从上到下的合法路径。

因此算法统计到的每条路径都符合题意。

结论 3：每条以当前节点结尾的合法路径都会被统计

考虑任意一条以当前节点结尾、和为 targetSum 的向下路径。

设这条路径开始前的祖先位置对应前缀和 previousPrefix。

根据路径和定义：

prefix - previousPrefix = targetSum

移项得到：

previousPrefix = prefix - targetSum

由于路径开始前的位置位于当前节点的祖先路径上，根据结论 1，这个前缀和已经记录在哈希表中。

算法查询 prefix - targetSum 时一定会找到它，并将对应次数加入答案。

所以每条以当前节点结尾的合法路径都会被统计。

结论 4：重复前缀和对应的路径会被正确区分

如果同一个前缀和在当前路径上出现多次，那么每个出现位置都可能作为一条合法路径的起点前一个位置。

这些位置不同，形成的路径也不同。

哈希表记录的是出现次数，而不是简单的存在性：

prefixCount[prefix - targetSum]

因此所有不同起点都能被分别计数。

结论 5：回溯保证不会统计跨分支路径

当前节点的左右子树属于不同的 DFS 分支。

处理完一个分支后，算法会把该分支新增的前缀和删除。

所以进入另一个分支时，哈希表中不会残留前一个分支的前缀和。

因此算法只会统计同一条根到当前节点路径上的连续向下路径，不会统计从一个分支跨到另一个分支的非法路径。

得出结论

由结论 1 可知，哈希表保存的信息范围正确。

由结论 2 可知，算法不会加入路径和错误的路径。

由结论 3 可知，所有合法路径都会被统计，不会遗漏。

由结论 4 可知，重复前缀和带来的多条路径能被正确区分。

由结论 5 可知，算法不会构造跨越不同分支的非法路径。

因此算法返回的 ans 正好是所有和为 targetSum 的向下路径数量。

举例理解

以：

root = [10,5,-3,3,2,null,11,3,-2,null,1]
targetSum = 8

为例，这棵树可以理解为：

        10
       /  \
      5   -3
     / \    \
    3   2    11
   / \   \
  3  -2   1

其中和为 8 的路径有：

5 -> 3
5 -> 2 -> 1
-3 -> 11

所以答案是：

3

以路径 10 -> 5 -> 3 为例：

• 到 10 时，前缀和是 10
• 到 5 时，前缀和是 15
• 到 3 时，前缀和是 18

在节点 3 处：

18 - targetSum = 18 - 8 = 10

前缀和 10 已经出现过，表示从 10 的下一个节点开始到当前节点的路径：

5 -> 3

其和是：

18 - 10 = 8

再看路径 5 -> 2 -> 1。

到 1 时，根到当前节点前缀和是：

10 + 5 + 2 + 1 = 18

此前在节点 10 的前缀和是 10，在当前路径上查到：

18 - 8 = 10

所以统计得到路径：

5 -> 2 -> 1

复杂度分析

解法一

外层 DFS 会把每个节点作为起点。

在最坏情况下，树退化成链，每个起点都会继续访问后面的所有节点。

• 时间复杂度：O(n^2)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈，其中 h 是树高。

解法二

前缀和解法只对每个节点进行一次 DFS 访问。

哈希表的查询和更新平均为 O(1)。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自 DFS 递归栈和当前路径上的前缀和哈希表。

哈希表最多保存 h + 1 个不同深度对应的前缀和，因此空间复杂度为 O(h)；最坏情况下 h = n。