我来给你讲解 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。

伪代码：

function pathSum(root, targetSum):
    if root is null: return 0
    
    // 以当前节点为起点的路径数 + 左子树的路径数 + 右子树的路径数
    return countPaths(root, targetSum) + 
           pathSum(root.left, targetSum) + 
           pathSum(root.right, targetSum)

function countPaths(node, target):
    if node is null: return 0
    
    count = 0
    if node.val == target:  // 当前节点单独构成路径
        count += 1
    
    // 继续向下寻找包含当前节点的路径
    count += countPaths(node.left, target - node.val)
    count += countPaths(node.right, target - node.val)
    
    return count

时间复杂度分析： O(n²)，对于每个节点都要遍历其所有子节点。

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

我们可以借鉴数组中子数组和问题的思路，使用前缀和来优化。

核心思想：

• 在遍历树的过程中，记录从根节点到当前节点的路径和（前缀和）
• 对于当前节点，我们要找的是：是否存在某个祖先节点，使得 当前前缀和 - 祖先前缀和 = targetSum
• 这等价于寻找是否存在祖先节点，其前缀和等于 当前前缀和 - targetSum

第四步：详细算法步骤

1. 定义前缀和映射：使用哈希表记录从根节点到当前路径上各个前缀和出现的次数
2. 深度优先遍历：递归遍历二叉树
3. 更新前缀和：在进入节点时，更新当前前缀和，并在哈希表中记录
4. 检查目标路径：检查是否存在 当前前缀和 - targetSum 的前缀和
5. 递归左右子树：继续遍历左右子树
6. 回溯：在返回前，从哈希表中移除当前前缀和（避免影响其他分支）

第五步：具体实现

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
        path_count = prefix_sum_count.get(current_sum - targetSum, 0)
        
        # 将当前前缀和加入哈希表
        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)

第六步：逐步示例分析

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

遍历到节点5时：

• 当前路径：10→5，前缀和=15
• 寻找：15-8=7，检查前缀和7出现的次数
• 路径10→5本身和=15≠8，但5→3路径和=8（15-7=8，其中7是路径10的前缀和）

关键理解：

• 前缀和7对应路径10（根节点）
• 当前前缀和15对应路径10→5
• 15-7=8正好是路径5→3的和（从节点10之后开始）

第七步：复杂度分析

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

第八步：关键要点总结

1. 前缀和思想：将树路径问题转化为前缀和差问题
2. 回溯的重要性：在返回前必须移除当前前缀和，避免影响其他分支
3. 初始条件：前缀和0出现1次，对应空路径的情况
4. 路径方向：只能从祖先到后代，符合前缀和的定义

这种方法巧妙地将树形结构问题转化为类似数组子数组和的问题，大大提高了效率。