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

题目描述

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

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

示例：

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

解题思路分析

第一步：理解问题核心

这个问题与简单的路径总和问题不同之处在于：

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

这意味着对于树中的每个节点，都可能作为路径的起点，路径可能经过该节点并向下延伸。

第二步：暴力解法思路

最直观的想法是：以每个节点作为路径起点，向下遍历所有可能的路径，检查路径和是否等于 targetSum。

暴力解法步骤：

1. 遍历树中的每个节点
2. 对于每个节点，作为路径起点，向下DFS搜索所有路径
3. 在DFS过程中，累加路径和，等于targetSum时计数+1

时间复杂度：O(n²)，最坏情况下每个节点都需要遍历其子树。

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

我们可以借鉴数组中的"前缀和"思想来优化：

核心洞察：对于从根节点到当前节点的路径和currSum，如果存在某个祖先节点到根节点的路径和prefixSum满足：

currSum - prefixSum = targetSum

那么从该祖先节点的下一个节点到当前节点的路径和就等于targetSum。

具体实现：

1. 使用哈希表记录从根节点到当前路径上各个节点的路径和出现的次数
2. 在DFS遍历过程中：
   • 计算从根节点到当前节点的路径和currSum
   • 检查currSum - targetSum是否在哈希表中，如果在，说明存在满足条件的路径
   • 更新哈希表，继续遍历子树
   • 回溯时从哈希表中移除当前节点的路径和

第四步：详细算法步骤

def pathSum(root, targetSum):
    from collections import defaultdict
    
    # 哈希表记录前缀和出现次数
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1  # 重要：空路径的和为0
    
    def dfs(node, curr_sum):
        if not node:
            return 0
            
        count = 0
        curr_sum += node.val  # 当前路径和
        
        # 检查是否存在满足条件的路径
        count += prefix_sum_count[curr_sum - targetSum]
        
        # 更新前缀和哈希表
        prefix_sum_count[curr_sum] += 1
        
        # 递归遍历左右子树
        count += dfs(node.left, curr_sum)
        count += dfs(node.right, curr_sum)
        
        # 回溯：移除当前节点的前缀和
        prefix_sum_count[curr_sum] -= 1
        
        return count
    
    return dfs(root, 0)

第五步：逐步演算示例

以示例树为例，targetSum = 8：

树结构：
      10
     /  \
    5    -3
   / \     \
  3   2     11
 / \   \
3  -2   1

遍历过程：

1. 根节点10：currSum=10，检查10-8=2（不存在），继续
2. 节点5：currSum=15，检查15-8=7（不存在）
3. 节点3：currSum=18，检查18-8=10（存在，计数+1）
4. 节点3：currSum=21，检查21-8=13（不存在）
5. 节点-2：currSum=16，检查16-8=8（不存在）
6. 回溯到节点5，继续右子树...
7. 最终找到3条路径

第六步：复杂度分析

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

第七步：关键要点总结

1. 前缀和思想：将树形问题转化为类似数组的前缀和问题
2. 回溯处理：必须在返回前从哈希表中移除当前节点的路径和
3. 初始化：前缀和为0的情况初始计数为1，对应从根节点开始的路径
4. 路径定义：路径是向下的，所以前缀和记录的是从根节点到当前节点的和

这种方法巧妙地将O(n²)的暴力解法优化到O(n)，是处理此类路径和问题的经典思路。