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)$。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

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

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.pathSum(root)
    print(result)

if __name__ == "__main__":
    main()