好的，我们接下来讲解 LeetCode 第 437 题：路径总和 III（Path Sum III）。

1. 题目描述

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

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

示例：

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

树的结构：

      10
     /  \
    5    -3
   / \     \
  3   2     11
 / \   \
3  -2   1

路径和为 8 的路径有：

• 5 → 3
• 5 → 2 → 1
• -3 → 11

因此返回 3。

2. 思路分析

2.1 直观理解

题目要求路径不一定从根开始，也不一定到叶子结束，只要是从上到下的连续节点就行。

一种直接的想法是：

• 以每个节点为路径的起点，向下 DFS 遍历，累加路径和，如果等于 targetSum 就计数。

这种方法的时间复杂度：

• 对每个节点作为起点，向下遍历它的子树，最坏情况（链状树）是 O(n) 深度。
• 总复杂度 O(n²)（n 为节点数）。

对于节点数较多时，可能不够高效。

2.2 优化思路：前缀和 + 回溯

我们可以利用 前缀和 的思想：

• 在遍历树时，记录从根节点到当前节点的路径和（称为前缀和）。
• 如果当前前缀和是 currSum，我们要找的是路径上是否存在一个祖先节点，它的前缀和是 currSum - targetSum。
• 如果有，说明从那个祖先节点的下一个节点到当前节点的路径和正好是 targetSum。

为什么可行？

• 假设根节点到当前节点的路径和为 currSum。
• 假设根节点到某个祖先节点的路径和为 prevSum。
• 那么从祖先节点的下一个节点到当前节点的路径和 = currSum - prevSum。
• 我们想让它等于 targetSum，即 currSum - prevSum = targetSum → prevSum = currSum - targetSum。

所以我们只需要在哈希表中记录遍历过程中出现的前缀和及其出现次数，就能 O(1) 时间找到满足条件的路径数量。

3. 解题步骤

1. 用一个哈希表 prefixSumCount 存储：前缀和 → 出现次数。
2. 初始时，前缀和 0 出现 1 次（表示空路径，方便处理从根节点开始的路径）。
3. DFS 遍历二叉树（前序遍历）：
   • 到达节点时，计算当前路径和 currSum。
   • 检查 currSum - targetSum 在哈希表中的次数，加到结果中。
   • 将 currSum 的出现次数 +1。
   • 递归左子树、右子树。
   • 回溯：在返回上一层前，将 currSum 的出现次数 -1（避免影响其他分支）。
4. 返回结果。

4. 详细例子演示

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

前缀和变化过程（DFS 顺序）：

1. 到 10：currSum = 10，要找 10 - 8 = 2，出现次数 0，结果 +0。哈希表：{0:1, 10:1}
2. 到 5：currSum = 15，找 15-8=7，出现次数 0，结果 +0。哈希表：{0:1, 10:1, 15:1}
3. 到 3：currSum = 18，找 18-8=10，出现次数 1（来自节点 10），结果 +1。哈希表：{0:1, 10:1, 15:1, 18:1}
4. 到 3（左3下的3）：currSum = 21，找 21-8=13，出现次数 0，结果 +0。哈希表：{0:1, 10:1, 15:1, 18:1, 21:1}
5. 回溯到 3（第一个3），哈希表恢复：{0:1, 10:1, 15:1, 18:1}
6. 到 -2：currSum = 16，找 16-8=8，出现次数 0，结果 +0。哈希表：{0:1, 10:1, 15:1, 18:1, 16:1}
7. 回溯到 5，哈希表恢复：{0:1, 10:1, 15:1}
8. 到 2：currSum = 17，找 17-8=9，出现次数 0，结果 +0。哈希表：{0:1, 10:1, 15:1, 17:1}
9. 到 1：currSum = 18，找 18-8=10，出现次数 1（来自节点 10），结果 +1。哈希表：{0:1, 10:1, 15:1, 17:1, 18:1}
10. 回溯到 2，哈希表恢复：{0:1, 10:1, 15:1}
11. 回溯到 10，哈希表恢复：{0:1, 10:1}
12. 到 -3：currSum = 7，找 7-8=-1，出现次数 0，结果 +0。哈希表：{0:1, 10:1, 7:1}
13. 到 11：currSum = 18，找 18-8=10，出现次数 1（来自节点 10），结果 +1。哈希表：{0:1, 10:1, 7:1, 18:1}

最终结果 = 1 + 1 + 1 = 3。

5. 代码实现（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
        
        prefixSumCount = defaultdict(int)
        prefixSumCount[0] = 1  # 空路径和为0出现1次
        self.result = 0
        
        def dfs(node, currSum):
            if not node:
                return
            
            currSum += node.val
            
            # 检查是否存在前缀和 currSum - targetSum
            self.result += prefixSumCount[currSum - targetSum]
            
            # 当前前缀和加入哈希表
            prefixSumCount[currSum] += 1
            
            # 递归左右子树
            dfs(node.left, currSum)
            dfs(node.right, currSum)
            
            # 回溯，移除当前前缀和
            prefixSumCount[currSum] -= 1
        
        dfs(root, 0)
        return self.result

6. 复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，哈希表存储前缀和，递归栈深度最坏 O(n)。

7. 总结

本题的关键在于将 路径和 问题转化为 前缀和差 问题，利用哈希表快速查找，从而将时间复杂度从 O(n²) 优化到 O(n)。

这种方法也适用于类似的子数组和/路径和问题，是重要的算法技巧。