LeetCode 面试题 04.12. 求和路径

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
深度优先搜索 树 二叉树

题目描述

✅ 面试题 04.12. 求和路径

image-20260929004957186

题意分析

统计节点值之和等于目标的非空路径数量。路径可以从任意节点开始，也可以在任意节点结束，但只能沿父到子的方向连续向下，不能从一个分支绕到另一个分支。

解法：祖先前缀和计数并回溯

核心思路

[!blue]

固定一个路径终点后，它的起点只可能是自己或某个祖先。若对每个终点重新枚举全部祖先会重复求和，可以把当前根到节点的路径看作一个数组，使用前缀和之差计算中间一段。

设从树根到当前节点的累计和为 s，某个候选起点的父节点处前缀和为 p，那么这段向下路径的和就是 s - p。要让它等于 target，只需找到前缀和为 s - target 的祖先位置。用 cnt 保存当前祖先路径中各前缀和的出现次数，一次查询就能得到以当前节点结尾的合法路径数量。

频次不能只记是否出现，因为不同祖先可能有相同前缀和，对应不同起点。开始登记一次空前缀 0，把根之前的虚拟位置也计入，才能统一统计从根开始的路径。

到达当前节点时，先把节点值加入 s，查询 cnt[s - target]，然后才登记当前的 s。顺序不能交换，否则目标为 0 时会把当前前缀与自身配对，误计一条没有节点的空路径。登记当前前缀后，左右孩子才能把它当作各自路径起点之前的位置。

左右子树处理完后，将当前 s 的次数减一，再返回父节点。这样计数表中有效的前缀始终只来自当前祖先链，兄弟分支不会互相拼接。每条合法路径恰好在它的终点被统计一次，把当前贡献与左右子树答案相加即可。

解题步骤

  1. 先登记空前缀 0 一次。
  2. 累加当前节点，先查询 s-target，再登记当前 s。
  3. 递归左右孩子并累加结果。
  4. 返回父节点前撤销当前前缀的一次计数。

空节点没有以它为终点的路径，返回 0。节点值可以为负数或 0，当前前缀和超过目标也不能提前停止；后面的节点仍可能把路径和拉回目标。

代码实现

class Solution {
    private Map<Long, Integer> cnt = new HashMap<>();
    private int target;

    public int pathSum(TreeNode root, int sum) {
        // 空前缀，用于统计从根开始的路径。
        cnt.put(0L, 1);
        target = sum;

        return dfs(root, 0);
    }

    private int dfs(TreeNode root, long s) {
        if (root == null) {
            return 0;
        }

        s += root.val;
        // 必须先查后写，否则 target 为 0 时会与自身配对。
        int answer = cnt.getOrDefault(s - target, 0);

        cnt.merge(s, 1, Integer::sum);

        answer += dfs(root.left, s);
        answer += dfs(root.right, s);

        // 回溯：让兄弟分支看不到本条链上的前缀和。
        cnt.merge(s, -1, Integer::sum);

        return answer;
    }
}

func pathSum(root *TreeNode, sum int) int {
    // 空前缀，用于统计从根开始的路径。
    cnt := map[int64]int{0: 1}
    var dfs func(*TreeNode, int64) int
    dfs = func(root *TreeNode, s int64) int {
        if root == nil {
            return 0
        }

        s += int64(root.Val)
        // 必须先查后写，否则 sum 为 0 时会与自身配对。
        answer := cnt[s-int64(sum)]
        cnt[s]++

        answer += dfs(root.Left, s)
        answer += dfs(root.Right, s)

        // 回溯：让兄弟分支看不到本条链上的前缀和。
        cnt[s]--
        return answer
    }
    return dfs(root, 0)
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，每个节点只做常数次哈希查询和计数更新。
  • 空间复杂度：总额外空间 $O(n)$。递归栈为 $O(h)$；代码没有删除计数降为 0 的键，映射最多保留 $O(n)$ 个曾出现的前缀。

关键点总结

[!green]

查询的是起点之前的祖先前缀，登记供后代使用，回溯时撤销以隔离兄弟分支。Java long 与 Go int64 保存累计和，避免多节点累加时溢出。

易错点总结

[!yellow]

  • 必须先查询再登记，否则 target=0 时会把空路径计入。
  • 离开节点时不撤销会让兄弟分支互相配对。
  • 负数和零都允许，不能按当前和大小剪枝。

相似题目

题目 难度 关联与区别
560. 和为 K 的子数组 中等 把数组前缀和计数推广到树路径，新增的是退出分支时的撤销。
113. 路径总和 II 中等 原题只找根到叶路径并输出方案，本题允许任意祖先起点且只计数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/92383421
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！