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

题目描述

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

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

示例：

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

解题思路分析

第一步：理解问题本质

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

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

这意味着对于树中的每个节点，都可能作为路径的起点，也可能作为路径的中间节点。

第二步：暴力解法思路

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

def pathSum(root, targetSum):
    if not root:
        return 0
    
    # 计算以当前节点为起点的路径数
    def count_paths(node, current_sum):
        if not node:
            return 0
        
        current_sum += node.val
        path_count = 1 if current_sum == targetSum else 0
        
        # 继续向左右子树探索
        path_count += count_paths(node.left, current_sum)
        path_count += count_paths(node.right, current_sum)
        
        return path_count
    
    # 以当前节点为起点
    paths_from_root = count_paths(root, 0)
    
    # 递归处理所有节点作为起点的情况
    paths_from_left = pathSum(root.left, targetSum) if root.left else 0
    paths_from_right = pathSum(root.right, targetSum) if root.right else 0
    
    return paths_from_root + paths_from_left + paths_from_right

时间复杂度分析：O(n²)，因为每个节点都要作为起点进行一次遍历。

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

我们可以借鉴数组问题中的前缀和思想。在遍历树的过程中，记录从根节点到当前节点的路径和（前缀和）。

关键观察：如果从根节点到当前节点的路径和是 current_sum，那么如果存在某个祖先节点到当前节点的路径和等于 targetSum，就意味着存在一个祖先节点，从根节点到该祖先节点的路径和是 current_sum - targetSum。

第四步：前缀和算法详细步骤

1. 使用哈希表记录路径和的出现次数
2. 深度优先遍历二叉树
3. 对于每个节点：
   • 计算从根节点到当前节点的路径和 current_sum
   • 检查 current_sum - targetSum 是否在哈希表中，如果在，说明存在符合条件的路径
   • 更新哈希表
   • 递归处理左右子树
   • 回溯时恢复哈希表状态（重要！）

第五步：具体实现

def pathSum(root, targetSum):
    from collections import defaultdict
    
    # 前缀和哈希表，记录路径和出现的次数
    prefix_sum_count = defaultdict(int)
    # 重要：初始状态，路径和为0的出现次数为1（空路径）
    prefix_sum_count[0] = 1
    
    def dfs(node, current_sum):
        if not node:
            return 0
        
        # 计算当前路径和
        current_sum += node.val
        
        # 查找符合条件的路径数量
        # 如果 current_sum - targetSum 存在，说明存在路径使得路径和 = targetSum
        path_count = prefix_sum_count[current_sum - targetSum]
        
        # 更新当前路径和的出现次数
        prefix_sum_count[current_sum] += 1
        
        # 递归处理左右子树
        path_count += dfs(node.left, current_sum)
        path_count += dfs(node.right, current_sum)
        
        # 回溯：恢复哈希表状态
        prefix_sum_count[current_sum] -= 1
        if prefix_sum_count[current_sum] == 0:
            del prefix_sum_count[current_sum]
        
        return path_count
    
    return dfs(root, 0)

第六步：算法复杂度分析

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

第七步：示例演示

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

遍历到节点5时：

• 路径和：10→5 = 15
• 查找 15-8=7 是否在哈希表中
• 此时哈希表中有：{0:1, 10:1, 15:1}
• 没有找到7，path_count=0

遍历到节点3时：

• 路径和：10→5→3 = 18
• 查找 18-8=10 是否在哈希表中
• 哈希表：{0:1, 10:1, 15:1, 18:1}
• 找到10出现1次，找到一条路径：5→3

第八步：关键要点总结

1. 前缀和思想：将路径和问题转化为两数之差问题
2. 哈希表记录：记录路径和的出现次数
3. 回溯恢复：遍历完子树后必须恢复哈希表状态
4. 初始状态：前缀和为0的出现次数初始为1，处理从根节点开始的路径

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