437. 路径总和 III

题目链接：437. 路径总和 III

题目描述

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

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

核心思考：前缀和 + DFS

本题最优的解法是利用**前缀和（Prefix Sum）**结合深度优先搜索（DFS）。

1. 什么是路径前缀和？
   从根节点到达当前节点 node 的路径上所有节点值的总和。
2. 转化问题：
   如果从根到当前节点的路径和为 s，我们想要寻找以当前节点为结尾且和为 targetSum 的连续路径，这等价于寻找在当前路径上是否存在一个祖先节点，其对应的前缀和为 s - targetSum。
3. 哈希表优化：
   使用哈希表 count 来记录当前路径上（即递归栈中）所有已经出现过的前缀和及其频率。
   • 在进入节点时：更新当前路径和 s，并在哈希表中查询满足条件的个数：ans += count[s - targetSum]。然后将 s 存入哈希表。
   • 回溯（Backtracking）的重要细节：在退出当前节点的递归（即返回父节点）之前，必须将当前路径和 s 在哈希表中的计数减 1。这是为了保证哈希表里记录的永远只是从根节点到当前节点这条“垂直”路径上的信息，防止跨越不同子树的分支路径互相干扰。

解题思路 (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
        count = defaultdict(int)
        count[0] = 1 # 初始化：前缀和为0的情况出现过1次
        ans = 0

        def dfs(node, s):
            if node is None:
                return
            
            nonlocal ans
            s += node.val
            # 查找在当前路径上方，是否存在前缀和为 s - targetSum 的位置
            ans += count[s - targetSum]
            
            # 将当前前缀和存入哈希表，并向下递归
            count[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)

            # 回溯：离开当前节点前，清空当前路径的记录，防止干扰其他分支
            count[s] -= 1
        
        dfs(root, 0)
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点只需被访问一次，且哈希表的存取操作为 $O(1)$。
• 空间复杂度：$O(N)$。在最坏情况下（树呈链状），哈希表和递归调用栈的大小均为 $O(N)$。