LeetCode LCR 050. 路径总和 III

约 8 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 树 二叉树 LCR
目录

题目描述

✅ LCR 050. 路径总和 III

题意分析

题目目标：统计二叉树中节点值之和等于 targetSum 的路径条数，路径必须自上而下（只能从父节点走向子节点），但起点不必是根、终点也不必是叶子。
核心约束：起点和终点都是自由的，这意味着候选路径的数量级是 $O(n^2)$，直接枚举两端会很贵；但"只能自上而下"这条限制又保证了任意一条合法路径必然是某条根到当前节点的链上的一段连续后缀，这正是可以用累计量做差的信号。
边界处理：节点值可以是负数，因此路径和不单调，绝不能因为"和已经超过目标"就剪枝；路径条数可能很大而中间累计和也可能超出 32 位范围；空树答案为 0；单个节点自身就是一条长度为 1 的合法路径。
实现取舍：真正需要回答的是"以当前节点为终点的路径中，有多少条的和恰好是目标"，把这个问题解决了，对所有节点求和就是答案。

解法：深度优先搜索

核心思路

暴力做法是以每个节点为起点各跑一次向下的搜索，累加和等于目标就计数。正确但代价是 $O(n^2)$，链状树上要做 $10^8$ 量级的操作，而且同一段路径的和被反复重算了很多遍。
瓶颈在于重复求和。观察"只能自上而下"这个限制：固定当前节点 v，从根到 v 的那条链是唯一的，任何以 v 结尾的合法路径都是这条链的一段后缀。记 s(x) 为根到节点 x 的累计和，那么从 u 的孩子一直走到 v 这条路径的和就是 s(v) - s(u)。要它等于 targetSum，等价于在 v 的祖先链（含根之前的虚拟起点）上找出满足 s(u) == s(v) - targetSum 的 u 的个数。
于是问题从"枚举两端"变成"在一条链上查某个累计值出现了几次"，用一张计数表就能 $O(1)$ 回答。由此确定不变量：递归进入节点 v 并完成自身累加后，计数表 cnt 中记录的恰好是从虚拟起点到 v 的父亲这条祖先链上所有累计和各自出现的次数，不多一个也不少一个。
维护这条不变量靠一进一出：进入 v 时先用 cnt[s - targetSum] 取答案（此刻表里只有祖先，不含自己，正好符合"路径至少包含 v 一个节点"的要求），再把 s 计入表中供子树使用；离开 v 前把 s 的计数减回去，这样兄弟子树看到的祖先链就不会被污染。表中预置 cnt[0] = 1，代表根之前那个和为 0 的虚拟起点，它让"以根为起点"的路径也能被同一套公式覆盖。

解题步骤

  • 初始化计数表并放入 cnt[0] = 1。为什么这一条必不可少：若某条路径恰好从根开始，它对应的 u 是根的"前一个位置"，累计和为 0；不预置这一项，所有从根出发的路径都会被漏掉。
  • 递归入口遇到空节点返回 0。为什么直接返回：空节点既不产生路径也不改变祖先链，返回加法单位元即可。
  • 进入节点先 s += node.val，得到根到当前节点的累计和。为什么必须先累加：后面的查询和记账都以"含当前节点"的累计值为准，顺序错了含义就变了。
  • 用 answer = cnt[s - targetSum] 取出以当前节点为终点的合法路径数。为什么此时查询：此刻表里装的严格是祖先链的累计值，查询结果自动排除了"空路径"和"跨分支路径"两类非法情况。
  • 再执行 cnt[s]++ 把自己加入表中。为什么必须在查询之后：先记账再查询的话，当 targetSum == 0 时会把"只包含自己且和为 0"的空路径误算一条。
  • 递归左右子树并把返回值累加进 answer。为什么两个子树可以共用同一张表：它们看到的祖先链前缀完全相同，而彼此的记录会在各自返回前被撤销。
  • 返回前执行 cnt[s]-- 撤销本节点的记账。为什么这一步是整个解法的关键：不撤销的话，左子树里的节点会被右子树当成祖先，统计出根本不存在于同一条链上的"路径"。
  • 以 具体用例：树 [10, 5, -3, 3, 2, null, 11]，targetSum = 8 走一遍。初始 cnt = {0:1}。进入 10，s = 10，查 cnt[2] 得 0，记入 cnt = {0:1, 10:1}。进入 5，s = 15，查 cnt[7] 得 0，记入 15。进入 3，s = 18，查 cnt[10] 得 1（对应祖先 10，即路径 5 -> 3，和为 8），答案加 1；记入 18 后两个孩子为空，撤销 18 返回。进入 2，s = 17，查 cnt[9] 得 0；记入 17，撤销后返回。回到 5 撤销 15。进入 -3，s = 7，查 cnt[-1] 得 0；记入 7。进入 11，s = 18，查 cnt[10] 得 1（对应祖先 10，即路径 -3 -> 11，和为 8），答案再加 1。注意此时表中不含左子树留下的 18，正是撤销操作保证了这一点。最终答案为 2，与手工枚举 5 -> 3 和 -3 -> 11 一致。

代码实现

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
    private Map<Long, Integer> cnt = new HashMap<>();
    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        cnt.put(0L, 1);
        this.targetSum = targetSum;
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, long s) {
        if (node == null) {
            return 0;
        }
        s += node.val;
        int answer = cnt.getOrDefault(s - targetSum, 0);
        cnt.merge(s, 1, Integer::sum);
        answer += dfs(node.left, s);
        answer += dfs(node.right, s);
        cnt.merge(s, -1, Integer::sum);
        return answer;
    }
}

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func pathSum(root *TreeNode, targetSum int) int {
    cnt := map[int]int{0: 1}
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, s int) int {
        if node == nil {
            return 0
        }
        s += node.Val
        answer := cnt[s-targetSum]
        cnt[s]++
        answer += dfs(node.Left, s) + dfs(node.Right, s)
        cnt[s]--
        return answer
    }
    return dfs(root, 0)
}

复杂度分析

  • 时间复杂度：$O(n)$。凭什么：每个节点只被访问一次，访问时做的是常数次哈希表查询与更新，把原本 $O(n^2)$ 的两端枚举压成了一次遍历。
  • 空间复杂度：$O(h)$，h 为树高，最坏为 $O(n)$。凭什么：计数表在任意时刻只保存当前祖先链上的累计值（每层最多一项），递归栈深度同样是树高。

关键点总结

  • "连续区间和等于目标"的计数问题，统一转化为"累计和之差等于目标"，再用哈希表统计历史累计值的出现次数；数组上是前缀和计数，树上就是祖先链计数，两者是同一个模型。
  • 树上的这类统计比数组多一件事——回溯撤销。进入时记账、离开时撤销，才能保证"历史"始终等于"当前祖先链"，而不是"已经访问过的所有节点"。
  • 预置一个和为 0 的虚拟起点，是让"从起点开始的整段"也能被差分公式覆盖的通用技巧，缺了它答案会稳定偏小。
  • 查询必须发生在把自己记账之前，这一顺序在 targetSum 为 0 时才暴露问题，属于典型的"用例不覆盖就发现不了"的坑。
  • 面试视角：面试官几乎一定会问"节点值有负数，能不能剪枝"。答案是不能，正因为不单调才必须走计数路线；同时要主动指出累计和可能超出 32 位（10^4 个节点、每个 10^9），Java 里用 long 作键、Go 里 int 天然是 64 位，这些都是加分细节。

易错点总结

  • 错误写法：不预置 cnt[0] = 1 → 树 [1] 且 targetSum = 1 时查 cnt[0] 得 0，返回 0 而不是 1，所有从根出发的路径全部丢失。
  • 错误写法：先执行 cnt[s]++ 再查询 cnt[s - targetSum] → targetSum = 0 时每个节点都会把自己算成一条和为 0 的"空路径"，树 [1, 2, 3] 返回 3 而正确答案是 0。
  • 错误写法：返回前忘记 cnt[s]-- → 树 [1, 2, -1] 中左子树留下的累计值被右子树当作祖先，统计出跨分支的伪路径，答案偏大。
  • 错误写法：把撤销写在两次递归之间 → 右子树看不到当前节点的记录，以当前节点为起点、终点在右子树的路径全部漏掉。
  • 错误写法：因为"和已经大于目标"就剪掉子树 → 树 [1, -2, 3] 且 targetSum = 2 时路径 1 -> -2 -> 3 合法，剪枝会直接漏掉它，负数让单调性假设失效。
  • 错误写法：Java 中把累计和声明为 int → 一条 $10^4$ 长的链上每个值为 $10^5$ 时累计和达到 $10^9$ 以上并继续增长，溢出成负数，哈希表命中完全错乱。
  • 错误写法：以每个节点为起点重跑一次向下搜索 → 结果正确但链状树上代价 $O(n^2)$，$10^4$ 个节点时约 $10^8$ 次操作，容易超时。
  • 错误写法：把计数表换成"祖先累计和的列表"再线性查找 → 语义正确但每个节点要扫一遍祖先链，复杂度退回 $O(nh)$，链状树同样退化。
  • 错误写法：允许路径自下而上或跨越拐点 → 树 [1, 2, 3] 且 targetSum = 5 时误把 2 -> 1 -> 3 算进去，返回 1 而正确答案是 0，题目要求路径必须单向向下。

相似题目

题目 难度 考察点
560. 和为 K 的子数组 中等 同一套前缀和计数模型的一维版本，无需回溯撤销
112. 路径总和 简单 路径两端固定为根与叶，只判存在性可提前返回
113. 路径总和 II 中等 需要输出具体路径，考察路径数组的回溯维护
LCR 049. 求根节点到叶节点数字之和 中等 前缀沿路下传但在叶子结算，不需要历史计数
1248. 统计「优美子数组」 中等 计数对象换成奇数个数的前缀，映射思路完全相同
687. 最长同值路径 中等 路径允许经过拐点，必须自底向上返回单臂长度