LeetCode 面试题 04.12. 求和路径

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 面试题 04.12. 求和路径

题意分析

给一棵二叉树和一个目标值，统计节点值之和等于目标值的路径数目。路径不必从根开始、也不必到叶子结束，但方向必须向下——只能沿父到子的方向延伸，不能拐弯经过某个节点的两侧。

「向下」这条约束是解题的支点：它意味着任意一条合法路径都可以由「根到某节点的前缀」减去「根到另一节点的前缀」得到，而这两个节点必须处于同一条根到叶的链上。换句话说，树上的路径问题在这里被压回成了一维数组上的子数组问题。

「不必从根开始」说明答案要在所有起点上累加，而不是在根处一次判定；「统计数目」而非「列出路径」，说明不需要保存路径本身，只需要计数——这为用哈希表做计数留出了空间。

节点值可以为负数，这一点必须留意：它排除了「和一旦超过目标就剪枝」这类基于单调性的优化，也意味着同一个前缀和可能在一条链上出现多次。目标值与节点值的量级还提示累加过程可能超出 32 位范围，需要用更宽的类型承载。

边界：空树答案为 0；单节点树当且仅当其值等于目标值时答案为 1；路径长度可以是 1，即单个节点自身。

解法：深度优先搜索

核心思路

朴素做法是「以每个节点为起点各做一次向下搜索」：外层遍历 n 个起点，内层从起点往下累加并统计命中。答案正确，复杂度 $O(n^2)$（链状树时更是稳稳的平方级）。瓶颈在于同一段路径的和被反复累加了很多次——起点每往上挪一格，整段又要重算一遍。

把「向下」这条约束用足：固定当前节点 x，从根到 x 的这条链就是一个一维序列，以 x 结尾的所有合法路径，正好对应这个序列的所有后缀。设 s 为根到 x 的前缀和，某条以 x 结尾的路径以节点 y 的孩子为起点，那么这条路径的和就是 s - (根到 y 的前缀和)。要它等于 target，就是要求存在 y 满足「根到 y 的前缀和等于 s - target」。

于是问题变成：在当前根到 x 的这条链上，有多少个祖先的前缀和等于 s - target。用一张哈希表 cnt 把这条链上出现过的前缀和计数存起来，查询就是 $O(1)$。这正是一维数组里「和为 K 的子数组」的做法搬到树上。

状态与不变量定死为：进入 dfs(x, s) 并累加完 x 的值之后，cnt 中记录的恰好是根到 x 的父节点这条链上所有前缀和的出现次数（含虚拟的空前缀 0）。这条不变量要求 cnt 只反映当前这条链，而不是已经访问过的全部节点——因此进入子树前把 s 计数加一、离开子树后必须减回去，这一加一减就是回溯。

初始时放入 cnt[0] = 1，代表长度为零的空前缀。它的作用是让「从根本身开始」的路径也能被统计到：此时 s - target 恰好为 0，需要有一个计数与之匹配。

解题步骤

预置空前缀：cnt.put(0L, 1)。缺了它，凡是从根出发的路径都会被漏掉。

递归基：节点为空返回 0，空子树贡献不了任何路径。

先累加再查询：s += root.val 之后立刻用 cnt.getOrDefault(s - target, 0) 取答案。顺序不能反——查询依据的是「以当前节点结尾」的前缀和。

查询必须早于写入：先查 s - target，再把 s 自身计入 cnt。若先写入，当 target 为 0 时当前节点会与自己配对，凭空多出一条长度为零的路径。

递归两个孩子并累加：左右子树各自返回的计数直接加进答案，因为路径不跨越当前节点的两侧，两边互不干扰。

回溯撤销：返回前把 cnt[s] 减一。这一步保证兄弟分支看不到彼此的前缀和，是全题唯一但也最关键的清理动作。

用宽类型累加：前缀和 s 用 long，避免深链上大量同号值相加时溢出。

以三节点树走一遍：根为 0，左孩子为 2，右孩子为 4，target = 2。人工数一遍答案：单点 [2] 命中、[0, 2] 命中，[0]、[4]、[0, 4] 都不命中，答案是 2。

初始 cnt = {0: 1}。进入根：s = 0，查 cnt[0 - 2] = cnt[-2] = 0，本层贡献 0；写入后 cnt = {0: 2}。

进入左孩子：s = 0 + 2 = 2，查 cnt[2 - 2] = cnt[0] = 2，一次拿到 2 条——分别对应以空前缀开头的 [0, 2] 和以根为前缀开头的 [2]。写入后 cnt = {0: 2, 2: 1}；两个孩子均为空各返回 0；返回前撤销，cnt = {0: 2, 2: 0}。

进入右孩子：s = 0 + 4 = 4，查 cnt[4 - 2] = cnt[2] = 0，不贡献。这里正是回溯的价值所在——如果没有把左孩子的前缀和 2 撤销掉，这次查询会得到 1，从而把「2 → 4」这条根本不存在的路径算进答案，输出 3。最终答案为 0 + 2 + 0 = 2，与人工计数一致。

代码实现

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[int]int{0: 1}
    var dfs func(*TreeNode, int) int
    dfs = func(root *TreeNode, s int) int {
        if root == nil {
            return 0
        }

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

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

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

复杂度分析

时间复杂度：$O(n)$，n 为节点数。每个节点只被访问一次，节点内部做常数次哈希查询与更新，把朴素的「每个起点各搜一遍」的 $O(n^2)$ 降到线性。

空间复杂度：$O(n)$，哈希表最多同时保存一条根到叶链上的前缀和，递归栈深度等于树高；链状树时两者都达到 $O(n)$。

关键点总结

「路径只能向下」意味着任意路径都是某条根到节点链上的一段连续区间，识别出这一点就能把树上问题直接翻译成一维的「和为 K 的子数组」，这是本题的核心转化。

哈希表里存的是当前这条链的前缀和，不是已访问过的全部节点；回溯时的减一操作正是维持这条不变量的手段，也是把它与普通前缀和题区分开的地方。

cnt[0] = 1 的空前缀不是凑数，它承载了「路径从根开始」这一类解；面试时能解释清楚它的含义，比记住要写这一行更重要。

先查询后写入的顺序，避免了当前节点与自身配对；在 target 为 0 或存在零值节点时，写反顺序会直接多计。

节点值可正可负，所以既不能靠「和超过目标就停」剪枝，也不能假设前缀和单调；累加时用 long 承载是防御深链溢出的常规做法。

面试里要能对比朴素双重递归与前缀和两种解法：前者好写、后者最优，主动说出「重复累加是瓶颈，用前缀和把它消掉」的推理过程，通常比直接甩出最优解得分更高。

易错点总结

忘记回溯减一：根为 0、左孩子 2、右孩子 4，target = 2 → 右孩子查到左孩子留下的前缀和 2，把不存在的「2 → 4」算成一条，答案从 2 变成 3。

缺少 cnt[0] = 1：单节点树 [5]，target = 5 → 查 cnt[0] 得 0，答案为 0，所有从根出发的路径全部漏掉。

先写入再查询：单节点树 [0]，target = 0 → 当前节点先把前缀和 0 计入，再查 cnt[0] 得 2，答案多出一条长度为零的伪路径。

在左右子树之间共用同一个可变 s 而不是按值传参：树 [1, 2, 3] → 左子树累加后的 s 被带进右子树，右侧前缀和变成 1 + 2 + 3，命中判定全错。

用 int 累加前缀和：一条由数万个接近 $10^5$ 的正值组成的链 → 前缀和溢出成负数，与哈希表中的键无法匹配，答案偏小。

把左右子树的返回值用取最大值合并：树 [1, 1, 1]，target = 1 → 两侧各有一条命中，取最大只得 1，正确答案是 3。

回溯时用 cnt.remove(s) 而不是减一：树中同一条链上出现两个相同前缀和（如值序列 1, 0）→ 一次删除抹掉了两次计数，祖先层的匹配随之丢失。

误以为路径可以拐弯：树 [1, 2, 3]，target = 5 → 若把 2 → 1 → 3 也算上会多出一条，本题只统计单向向下的路径。

想靠「和已超过目标」剪枝：树 [10, -10, null, null, 5] 这类含负值的链 → 走到 10 就停会漏掉后面靠负数拉回来的解。

把哈希表建成全局且跨用例不清空：连续调用两次 pathSum → 第二次沿用了第一次残留的计数，答案偏大。

相似题目

题目	难度	考察点
437. 路径总和 III	中等	与本题同题，是这套「树上前缀和 + 回溯」模板的原型
560. 和为 K 的子数组	中等	一维版本，没有回溯动作，最能看清前缀和计数的本质
112. 路径总和	简单	路径必须从根到叶且只问存在性，一次带累加值的递归即可
113. 路径总和 II	中等	要输出路径本身，重点从计数转向 `path` 的追加与撤销
129. 求根节点到叶节点数字之和	中等	累加规则从加法变成乘十进位，同样是自顶向下传递状态
124. 二叉树中的最大路径和	困难	路径允许在某点拐弯，必须区分「返回给父亲的单链」与「全局答案」
LCR 050. 路径总和 III	中等	与 437 同题，可直接套用本题写法