我来给你讲解 LeetCode 第 437 题：路径总和 III。

题目描述

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

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

示例：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：有 3 条路径之和等于 8：
- 5 → 3
- 5 → 2 → 1  
- -3 → 11

解题思路分析

第一步：理解问题核心

这个问题与简单的路径总和问题不同，因为：

1. 路径不一定从根节点开始
2. 路径不一定在叶子节点结束
3. 路径必须是向下的（父节点到子节点）

这意味着对于树中的每个节点，都可能存在以该节点为终点的路径满足条件。

第二步：暴力解法思路

最直观的想法是：对于树中的每个节点，都检查以该节点为终点的所有路径。

暴力解法步骤：

1. 遍历树中的每个节点（前序遍历）
2. 对于每个节点，向上遍历到根节点，计算路径和
3. 如果路径和等于 targetSum，计数加一

这种方法的时间复杂度是 O(n²)，对于每个节点都要向上遍历到根节点。

第三步：优化思路 - 前缀和技巧

我们可以使用前缀和的思想来优化：

核心思想：

• 在遍历树的过程中，记录从根节点到当前节点的路径和（前缀和）
• 如果存在一个前缀和 prefix_sum - targetSum，那么从那个节点到当前节点的路径和就是 targetSum

具体步骤：

1. 使用哈希表记录每个前缀和出现的次数
2. 深度优先遍历二叉树
3. 对于每个节点：
   • 计算当前前缀和
   • 检查 当前前缀和 - targetSum 是否在哈希表中
   • 更新哈希表
   • 递归遍历左右子树
   • 回溯时恢复哈希表（重要！）

第四步：详细算法实现

def pathSum(root, targetSum):
    from collections import defaultdict
    
    def dfs(node, curr_sum):
        if not node:
            return 0
        
        nonlocal count
        # 当前路径和
        curr_sum += node.val
        
        # 检查是否存在前缀和满足 curr_sum - prefix_sum = targetSum
        # 即 prefix_sum = curr_sum - targetSum
        count += prefix_count[curr_sum - targetSum]
        
        # 将当前前缀和加入哈希表
        prefix_count[curr_sum] += 1
        
        # 递归遍历左右子树
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)
        
        # 回溯，移除当前前缀和
        prefix_count[curr_sum] -= 1
    
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # 重要：空路径的前缀和为0
    count = 0
    dfs(root, 0)
    return count

第五步：逐步解释代码逻辑

1. 初始化前缀和哈希表

prefix_count = defaultdict(int)
prefix_count[0] = 1  # 空路径的和为0

• 为什么需要 prefix_count[0] = 1？
• 考虑路径从根节点开始的情况：如果从根节点到当前节点的和正好等于 targetSum，那么我们需要 curr_sum - targetSum = 0 存在。

2. 深度优先遍历

curr_sum += node.val
count += prefix_count[curr_sum - targetSum]

• 计算到当前节点的路径和
• 检查是否存在某个前缀和，使得从那个节点到当前节点的和等于 targetSum

3. 回溯操作

prefix_count[curr_sum] -= 1

• 在返回上一层递归前，移除当前节点的前缀和
• 确保哈希表只包含当前路径上的前缀和

第六步：示例演示

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

遍历到节点 5 时：

• 当前路径和：10 + 5 = 15
• 检查 15 - 8 = 7 是否在哈希表中（此时不在）
• 继续遍历...

遍历到节点 3 时（路径 10→5→3）：

• 当前路径和：10 + 5 + 3 = 18
• 检查 18 - 8 = 10，发现 10 在哈希表中（从根节点 10 到当前节点 3）
• 找到一条路径：5→3（和=8）

第七步：复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(n)，哈希表的大小和递归栈的深度

第八步：关键要点总结

1. 前缀和思想：将路径和问题转化为两前缀和之差的问题
2. 回溯的重要性：确保哈希表只包含当前路径的前缀和
3. 空路径处理：prefix_count[0] = 1 处理从根节点开始的路径
4. 路径方向：路径必须是向下的，所以使用深度优先遍历是合适的

这种方法将时间复杂度从 O(n²) 优化到 O(n)，是典型的用空间换时间的优化策略。