437. 路径总和 III (Medium)

专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/path-sum-iii/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示：

• 二叉树的节点数范围为 [0, 1000]
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000

---

题目详细分析

• 数据范围含义： 最多 1000 个节点，节点值范围 [-10^9, 10^9]，可能非常大，累加可能超过 32 位整数范围，需要用 Python 的 int（任意精度）。
• 输入输出特征： 输入根节点和 targetSum，输出路径数量（整数）。路径不需要从根开始或到叶子结束。
• 边界条件： 空树返回 0。单节点如果值等于 targetSum 返回 1，否则返回 0。
• 核心约束： 路径必须向下（从父到子），不能向上回溯。限制了这个问题的解法只能用 DFS 从上往下记录，不能随意组合。
• 隐藏条件： 节点值有正有负。这意味着不能通过「当前和已经超过 targetSum」来剪枝，因为后面可能出现负数让和变小。

---

小白版直白理解

就像在一棵许愿树上找礼物——每个节点上挂着一个数字牌子。你想找一些连续的从上到下的分支，使分支上的数字加起来正好是你的幸运数字。可以从任何节点开始（不一定从树根），在任何节点结束（不一定要到叶子）。你需要数出有多少条这样的分支。

因为树上的数字可能是负数，所以即使当前加起来已经超过了幸运数字，继续往下可能又变回幸运数。

---

解题思路

思路一：前缀和 + DFS + 回溯（推荐）

核心思想： 在 DFS 遍历的过程中，维护从根节点到当前节点的路径和（前缀和 cur_sum）。用哈希表记录「前缀和 → 出现次数」。对于当前节点，cur_sum - targetSum 在前缀和中的出现次数，就是以当前节点结尾的满足条件的路径数。

为什么能这样做？ 想象从根到当前节点的路径和为 S，如果存在一个祖先节点，从根到该祖先的路径和为 S - targetSum，那么从该祖先的下一个节点到当前节点的路径和就是 targetSum。这正是数组中「和为 K 的子数组」问题在树上的推广。

为什么需要回溯？ 左右子树遍历完后，当前路径就不再存在了，必须把当前前缀和的计数减回去，否则其他分支会错误地使用这条路径的信息。

from collections import defaultdict
 
def pathSum(root, targetSum):
    # 前缀和字典：记录从根到当前节点的路径和出现的次数
    prefix = defaultdict(int)
    prefix[0] = 1  # 空路径的前缀和为 0
 
    def dfs(node, cur_sum):
        if not node:
            return 0
 
        # 更新当前路径和
        cur_sum += node.val
        # 以当前节点结尾的满足条件的路径数
        count = prefix[cur_sum - targetSum]
 
        # 记录当前前缀和
        prefix[cur_sum] += 1
        # 递归处理左右子树
        count += dfs(node.left, cur_sum)
        count += dfs(node.right, cur_sum)
        # 回溯：移除当前前缀和（左右子树已经处理完毕）
        prefix[cur_sum] -= 1
 
        return count
 
    return dfs(root, 0)

思路二：双重递归（暴力解法）

以每个节点为起点，向下找所有路径。外层递归遍历每个节点作为起点，内层递归从该节点出发向下搜索。

优缺点： 思路简单直观，但时间复杂度 O(n^2)（退化情况下），适合 n 较小时使用。

def pathSum(root, targetSum):
    if not root:
        return 0
 
    # 以当前节点为起点，向下搜索
    def dfs_from_node(node, target):
        if not node:
            return 0
        count = 1 if node.val == target else 0
        # 继续向下（允许负数，所以即使 target - node.val 有可能不等于 0 也要继续）
        count += dfs_from_node(node.left, target - node.val)
        count += dfs_from_node(node.right, target - node.val)
        return count
 
    # 以每个节点为起点 + 递归处理左右子树
    return (dfs_from_node(root, targetSum) +
            pathSum(root.left, targetSum) +
            pathSum(root.right, targetSum))

---

易错点

• prefix[0] = 1 的含义： 表示「空路径的前缀和为 0 出现过一次」。这样当 cur_sum == targetSum 时，prefix[cur_sum - targetSum] = prefix[0] = 1，正确计数了从根节点到当前节点的路径。
• 回溯时必须 prefix[cur_sum] -= 1： 如果忘记回溯，其他分支会错误地计入当前分支的前缀和。这是树上用前缀和最容易犯的错误（区别于数组上的前缀和不需要回溯）。
• 节点值可能为负数： 双重递归法不能通过 target - node.val == 0 来终止递归，因为后面可能负数让和归零再变成 targetSum。
• 数值溢出： 节点值范围 [-10^9, 10^9]，1000 个节点累加可能达到 ±10^12，Python 无问题，但 C++/Java 需要用 long。
• 前缀和字典不要用 list 替代： 因为需要的是「出现次数」的累加，不是位置索引。

---

框架提炼

树上前缀和模板（对应数组上的「和为 K 的子数组」）：

from collections import defaultdict
 
def pathSum(root, targetSum):
    prefix = defaultdict(int)
    prefix[0] = 1  # 空路径
 
    def dfs(node, cur_sum):
        if not node:
            return 0
        cur_sum += node.val
        count = prefix[cur_sum - targetSum]  # 关键：查找之前出现过的前缀和
        prefix[cur_sum] += 1                 # 记录当前前缀和
        count += dfs(node.left, cur_sum)
        count += dfs(node.right, cur_sum)
        prefix[cur_sum] -= 1                 # 回溯
        return count
 
    return dfs(root, 0)

对比数组版本（560-和为K的子数组）：

• 数组：一次遍历，不需要回溯（不会走回头路）
• 树：DFS 遍历，需要回溯（不同分支要隔离）

这是因为树上有多条分支，数组只有一条路。

---

关联题目

• 560-和为K的子数组 — 同一思想在数组上的体现，树的版本是数组版本的推广。先理解「和为 K 的子数组」，再理解树上的前缀和就很容易。
• 124-二叉树中的最大路径和 — 同样是在树上做路径统计，但 124 求的是最大值、可以拐弯（经过根连接左右），而本题求的是个数、只能向下不能拐弯。
• 面试题 04.12-求和路径 — 与本题完全相同的题目，不同出版社的题号。