跳到主要内容

LeetCode 437. 路径总和 III

本节目标

将向下路径和改写为前缀和之差，并在递归回程撤销当前路径的登记。

这是树上综合问题中把路径计数转化为前缀差的题目；路径只能向下，但可以从任意节点开始、在任意节点结束。

查看 LeetCode 原题

题意与边界​

需要统计和为 targetSum 的向下路径数量。负数、重复前缀和和不从根开始的路径都合法；不能只在叶子或根节点检查。

前缀登记与撤销​

设 currentSum 为根到当前节点的前缀和。若某个祖先之前的前缀为 currentSum - targetSum，两者之间的路径和恰为目标值。因此哈希表保存当前递归路径上每个前缀和的出现次数，初始登记 0: 1，表示从根开始的路径。

进入节点后先累加答案，再登记当前前缀；递归左右子树后必须把当前前缀计数减一。登记与撤销成对，保证哈希表始终只描述根到当前节点这一条路径，不会把左子树的状态带进右子树。C++ 使用 long long 保存前缀和，避免累加溢出。

正确性依据​

在任一节点，当前路径上每个历史前缀都对应一个唯一可作为起点的位置；恰好等于 currentSum - targetSum 的前缀数量就是以当前节点为终点的合法路径数量。递归枚举每个终点一次，故所有合法路径恰好被计数一次。回程撤销后，兄弟子树不再看见不属于其祖先链的前缀，保持统计范围正确。

代码实现​

C++17
class Solution {
public:
    int pathSum(TreeNode* root, long long targetSum) {
        target = targetSum;
        answer = 0;
        prefixCount.clear();
        prefixCount[0] = 1;
        dfs(root, 0);
        return answer;
    }

private:
    long long target;
    int answer;
    std::unordered_map<long long, int> prefixCount;

    void dfs(TreeNode* node, long long currentSum) {
        if (node == nullptr) {
            return;
        }

        currentSum += node->val;
        answer += prefixCount[currentSum - target];
        prefixCount[currentSum]++;
        dfs(node->left, currentSum);
        dfs(node->right, currentSum);
        prefixCount[currentSum]--;
    }
};

复杂度分析​

每个节点进行常数次哈希表操作，时间复杂度为 O(n)。当前根到节点路径上的非零有效前缀至多有 O(h) 个，递归栈也为 O(h)；但代码不会删除回程后计数归零的历史键，哈希表总键数最坏为 O(n)，因此额外空间最坏为 O(n)。

边界与易错点​

  • 忘记初始 0: 1，漏掉从根开始的路径。
  • 只用集合不记录出现次数，漏掉重复前缀产生的多条路径。
  • 递归回程没有撤销，错误地跨兄弟子树计数。
  • 用 int 累加深树前缀，可能溢出。

模式迁移​

数组中的“和为 K 的子数组”也使用相同的前缀差。树上区别在于状态只对当前根到节点路径有效，因此需要递归回程撤销。