好的，我们这次来详细讲解 LeetCode 第 437 题「路径总和 III」。

1. 题目描述

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

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示（示例图略，可参考 LeetCode 原题图）。

提示：

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

2. 题目理解与思路分析

2.1 关键点

• 路径不一定从根开始，也不一定到叶子结束。
• 路径必须是 parent → child 的向下顺序。
• 节点值可能为负数，所以不能通过“当前和大于 targetSum 就剪枝”。

2.2 初步思路

一个直观的暴力解法是：

• 以每个节点为路径的起点，向下 DFS 遍历，累加路径和，如果和等于 targetSum，就计数一次。
• 这样时间复杂度是 O(N²)，最坏情况（链表形态）会达到 O(N²)，N 最大 1000，可能勉强通过，但我们可以优化。

2.3 优化思路

我们可以利用“前缀和”思想（常用在数组的连续子数组和问题），这里用在树的路径上：

前缀和定义：从根节点到当前节点的路径上所有节点值的和。

如果我们知道从根到当前节点 B 的前缀和 currSum，以及从根到路径上某一祖先节点 A 的前缀和 prefixSum，那么路径 A→B 的和就是 currSum - prefixSum。

我们要找 currSum - prefixSum = targetSum，即：

\[prefixSum = currSum - targetSum \]

也就是说，在从根到当前节点的路径上，如果存在一个前缀和等于 currSum - targetSum，就说明存在一个以当前节点为终点、向上到某一祖先的路径，其和正好为 targetSum。

3. 解法步骤详解

3.1 算法步骤

1. 用一个哈希表 prefixCount 记录从根节点到当前节点路径上各个前缀和出现的次数。
2. 递归遍历二叉树（前序遍历）：
   • 到达节点时，计算当前路径和 currSum。
   • 检查 currSum - targetSum 在 prefixCount 中的次数，累加到结果。
   • 将当前 currSum 的出现次数 +1。
   • 递归处理左右子树。
   • 回溯：在返回前，将当前 currSum 的出现次数 -1（避免影响其他分支）。
3. 递归开始时，prefixCount 初始应有 {0: 1}，表示路径和 0 出现一次（空路径），这样可以处理从根节点开始的路径。

3.2 举例说明

示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

我们手动推演一部分：

• 从根 10 开始：
  • currSum = 10，查 10-8=2，出现次数 0，结果 +0。
  • prefixCount: {0:1, 10:1}
• 进入左子树 5：
  • currSum = 15，查 15-8=7，出现次数 0，结果 +0。
  • prefixCount: {0:1, 10:1, 15:1}
• 进入 5 的左子树 3：
  • currSum = 18，查 18-8=10，出现次数 1（来自根 10），结果 +1。
  • prefixCount: {0:1, 10:1, 15:1, 18:1}
• 继续向下可找到其他路径。

4. 代码实现（Python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        from collections import defaultdict
        
        # 哈希表记录前缀和出现次数
        prefixCount = defaultdict(int)
        prefixCount[0] = 1  # 空路径和0，用于处理从根开始的路径
        self.count = 0
        
        def dfs(node, currSum):
            if not node:
                return
            
            currSum += node.val
            # 查找需要的互补前缀和
            self.count += prefixCount[currSum - targetSum]
            
            # 将当前前缀和加入哈希表
            prefixCount[currSum] += 1
            
            # 递归左右子树
            dfs(node.left, currSum)
            dfs(node.right, currSum)
            
            # 回溯，移除当前前缀和
            prefixCount[currSum] -= 1
        
        dfs(root, 0)
        return self.count

5. 复杂度分析

• 时间复杂度：O(N)，每个节点访问一次。
• 空间复杂度：O(N)，哈希表空间以及递归栈空间。

6. 总结

本题的关键是将“任意向下路径和”转化为“前缀和差值”问题，利用哈希表将查找时间降为 O(1)，从而将整体复杂度从 O(N²) 优化到 O(N)。
同时注意回溯时要恢复状态，避免不同分支间的干扰。