LeetCode 437. 路径总和 III

约 6 分钟
文章信息 14 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 10-20 字节跳动 微软 快手 腾讯 猿辅导 拼多多 网易 LeetCode 75 LeetCode 热题 100
标签
深度优先搜索 树 二叉树 前缀和 二叉树路径总和问题
目录

题目描述

✅ 437. 路径总和 III

image-20250418223726189

image-20250418223739920

题意分析

给定一棵二叉树和一个整数 targetSum，统计树中「节点值之和等于 targetSum」的路径条数。

这里的路径定义是本题全部难点所在，必须逐字读清楚：路径可以从任意节点开始、在任意节点结束，但方向必须向下。也就是说，路径的两个端点之间必须是严格的祖先—后代关系，只能顺着父指向子的方向一路走，不允许先向上走到某个祖先再折下去。因此路径不必从根开始，也不必到叶子结束，但它一定是某条「根到叶」链路上的一段连续区间。

约束信号有两条。一是节点值可正可负（范围到 $\pm 10^9$），这直接封死了任何依赖「和单调递增」的剪枝或双指针写法。二是节点数最多 1000 而节点值可达 $10^9$，路径和最大能到 $10^{12}$ 量级，超出 32 位整数范围，中间量必须用 64 位整数承载。

边界情况：空树返回 0；targetSum 为 0（此时值为 0 的单节点自身就是一条合法路径）；路径只包含一个节点；同一条链上存在多条互相嵌套的合法路径，它们要分别计数。

解法：DFS + 前缀和回溯

核心思路

对每个节点都重新向下枚举路径，最坏需要 $O(n^2)$。重复计算来自同一条根到当前节点的链，可以借用“和为 K 的子数组”的前缀和思想一次统计。

设当前节点的根路径前缀和为 prefix。若某个祖先位置的前缀和为 prefix - targetSum，那么该位置之后到当前节点的路径和恰好为 targetSum。哈希表 count 记录当前递归链上每种前缀和出现的次数，因此当前节点作为终点时，新增答案为：

count[prefix - targetSum]

树与数组的区别在于分支：左子树中的前缀不能用于右子树。进入节点时加入当前前缀，离开节点时将其计数减一，保证表中始终只保留当前根路径上的有效计数。初始化 count[0] = 1，表示根节点之前的空前缀，使从根开始的路径也能被统计。

不变量与正确性：查询当前节点时，count 中恰好包含它所有祖先位置的前缀和。每个被命中的前缀唯一对应一条以当前节点为终点、和为目标值的向下路径；每条合法路径也会在访问其终点时被命中一次。因此所有路径被统计一次且仅一次。

解题步骤

  • 初始化哈希表 count = {0: 1}，从根节点开始 DFS，当前前缀和为 0。
  • 到达节点后把节点值累加到 prefix。
  • 查询 count[prefix - targetSum]，得到以当前节点结尾的合法路径数。
  • 将 count[prefix] 加一，再递归左右子树。
  • 返回上一层前将 count[prefix] 减一，撤销当前节点对兄弟分支的影响。

例如当前根路径的前缀依次为 0, 10, 15, 18，目标值为 8。访问前缀 18 的节点时查找 10，命中一次，对应的路径就是前缀 10 之后到当前节点的那一段，路径和为 18 - 10 = 8。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> count = new HashMap<>();
        count.put(0L, 1);
        return dfs(root, 0L, targetSum, count);
    }

    private int dfs(TreeNode node, long prefix, int target,
                    Map<Long, Integer> count) {
        if (node == null) {
            return 0;
        }

        prefix += node.val;
        int answer = count.getOrDefault(prefix - target, 0);
        count.put(prefix, count.getOrDefault(prefix, 0) + 1);

        answer += dfs(node.left, prefix, target, count);
        answer += dfs(node.right, prefix, target, count);

        count.put(prefix, count.get(prefix) - 1);
        return answer;
    }
}

func pathSum(root *TreeNode, targetSum int) int {
    count := map[int64]int{0: 1}

    var dfs func(*TreeNode, int64) int
    dfs = func(node *TreeNode, prefix int64) int {
        if node == nil {
            return 0
        }

        prefix += int64(node.Val)
        answer := count[prefix-int64(targetSum)]
        count[prefix]++

        answer += dfs(node.Left, prefix)
        answer += dfs(node.Right, prefix)

        count[prefix]--
        return answer
    }

    return dfs(root, 0)
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点访问一次，每次只做常数次哈希操作。
  • 空间复杂度：$O(n)$。哈希表最坏记录 $O(n)$ 种前缀和，递归栈最深为树高 $O(h)$。

关键点总结

  • 固定路径终点后，用“当前前缀减目标值”反查所有合法起点。
  • 哈希表存的是当前祖先链，不是整棵树的全局统计；递归返回时必须回溯撤销。
  • count[0] = 1 负责统计从根节点开始的路径。
  • 节点值和路径长度可能让前缀和超过 32 位，Java 用 long，Go 用 int64。
  • 先查询、再加入当前前缀，避免 targetSum = 0 时把空路径算进去。

易错点总结

  • 忘记回溯减一：兄弟子树会把彼此的节点误当成祖先，统计出并不存在的跨分支路径。
  • 回溯时直接删除键：同一条链上可能有重复前缀和；应减计数，不能删除其他祖先留下的同值记录。
  • 漏掉 count[0] = 1：所有从根开始且和为目标值的路径都会少算。
  • 使用 32 位前缀和：节点值累加可能溢出，导致哈希查询错误。
  • 使用滑动窗口：节点值允许为负，路径和不具备单调性，窗口无法安全收缩。

相似题目

题目 难度 考察点
560. 和为 K 的子数组 中等 本题的一维原型，前缀和加哈希表且无需回溯撤销
112. 路径总和 简单 路径固定为根到叶，只需判断存在性
113. 路径总和 II 中等 根到叶且要求输出全部方案，考回溯时的路径数组维护
LCR 050. 路径总和 III 中等 与本题同题异号，可直接复用同一份代码
面试题 04.12. 求和路径 中等 与本题同题异号，常被用来对比暴力双递归与前缀和两种解
124. 二叉树中的最大路径和 困难 路径允许经过父节点折返，前缀和失效，改用后序返回增益
129. 求根节点到叶节点数字之和 中等 同为沿链累积，累积方式从相加换成按位进制拼接
974. 和可被 K 整除的子数组 中等 哈希键从前缀和本身换成前缀和的模，需处理负数取模