LC437　路径总和 III¶

中等通过率 49.3%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索二叉树

牛客原题　源码

讲解章节：树的基础与遍历

一句话

把「向下路径的和」换成两个前缀和之差，边走边用哈希表数。

解题思路¶

这题考什么¶

路径必须自上而下，但起点、终点都不限。朴素做法是以每个节点为起点各下探一遍， n 个起点乘上 O(h) 的下探，链状树下就是 O(n^2)。

换个视角：记 s(x) 为「从根到 x 的路径和」（前缀和）。固定当前节点 cur，对根到 cur 这条链上的任一祖先 a，从 a 的孩子走到 cur 这一段的和恰好是 s(cur) - s(a)。要它等于 targetSum，就是要

s(a) = s(cur) - targetSum

于是问题变成：在当前这条从根到 cur 的链上，前缀和等于 s(cur) - targetSum 的节点有几个。用一张「前缀和 -> 出现次数」的表随深度优先搜索（DFS）动态维护这条链，每个节点只查一次表，总时间降到 O(n)。这套「前缀和配哈希表数区间」的套路与数组上的 LC560 完全同源，区别只是「区间」从数组的一段变成了树上的一条竖直链；哈希表的性质见哈希表。

表里必须预置一项 {0: 1}，代表长度为 0 的「空前缀」，对应「路径从根本身开始」的情形；少了它，所有以根为起点的合法路径都会漏数。

示例 2：root = [5,4,8,11,null,13,4,7,2,null,null,5,1]，targetSum = 22。

走到 7 时链是 5, 4, 11, 7，前缀和依次 5, 9, 20, 27；
查 27 - 22 = 5，表里有一个（根的 5），对应路径 4 -> 11 -> 7。
同理数出 5 -> 4 -> 11 -> 2 与 5 -> 8 -> 4 -> 5，共 3 条，与样例一致。

数据规模与复杂度¶

节点数在 [0, 1000]，节点值在 [-10^9, 10^9]，targetSum 在 [-1000, 1000]。每个节点入栈两次（下探一次、回退一次）、查表一次，时间 O(n)；表里同时存在的项数不超过当前链长，空间 O(h)，链状树退化到 O(n)。节点值到 1e9 而一条链可以有 1000 个节点，前缀和的量级到 1e12 —— Python 的整数没有溢出问题，但用固定宽度整型的语言这里必须开 64 位。

坑在哪¶

必须回退。表描述的是「当前这条从根往下的链」，离开一个节点时要把它的前缀和计数减回去。不减的话，左子树留下的前缀和会被右子树查到，数出根本不存在的路径 —— 那两段并不在同一条竖直链上。
{0: 1} 这个初值不能省。它代表空前缀，示例 2 里从根 5 起头的 5 -> 4 -> 11 -> 2 就是靠它数出来的；漏掉它，凡是从根开始的路径全丢。
查表必须发生在把自己的前缀和记进表之前。表里此刻应当只有真正的祖先与那个空前缀。若先记后查，targetSum 为 0 时会把 s(cur) 自己匹配上，数出一条长度为 0 的空路径 —— 而 targetSum 的取值范围恰好包含 0。
不能用任何单调性剪枝。节点值可以是负的，路径和沿路上下起伏，「和已经超过 targetSum 就不必再往下」这类想法在本题不成立。
空树返回 0。题面节点数下界是 0。这份写法天然满足：栈里唯一的元素是 None，第一轮就被跳过。
n 到 1000，链状树的递归深度恰好顶到 CPython 默认的 1000 层上限，再加上判题环境在题解外面还套着若干层调用，递归写法正处在会不会炸的边界上，所以这里用显式栈；递归改迭代见 DFS 深度优先搜索的 60.4 节。

参考实现¶

solutions/leetcode/LC437/sol.py
from typing import List, Optional


class Solution:
    def pathSum(self, root: "Optional[TreeNode]", targetSum: int) -> int:
        count = 0
        # 「根到某节点的前缀和 -> 它在当前这条链上出现过几次」。
        # 预置 {0: 1} 代表空前缀，对应「路径从根自己开始」的情形，漏了会少数一批
        seen = {0: 1}
        # 栈元素是 (节点, 到父节点为止的前缀和, 是否是回退帧)。
        # 回退帧携带的是该节点自己的前缀和，用来把计数减回去
        stack = [(root, 0, False)]
        while stack:
            node, pre, leaving = stack.pop()
            # 空子树没有前缀和可记，直接跳过；root 为 None 时也走这一条
            if node is None:
                continue
            if leaving:
                # 离开这个节点，它不再属于「当前链」，把它的计数还原
                seen[pre] -= 1
                continue
            # 根到当前节点的前缀和
            total = pre + node.val
            # 先查后记：表里此刻只有真正的祖先与空前缀。
            # 顺序反过来的话，targetSum 为 0 时会匹配上自己，多数一条空路径
            count += seen.get(total - targetSum, 0)
            seen[total] = seen.get(total, 0) + 1
            # 回退帧先压、两棵子树后压 —— 栈后进先出，子树全部处理完它才被弹出
            stack.append((node, total, True))
            stack.append((node.left, total, False))
            stack.append((node.right, total, False))
        return count

LC437 路径总和 III¶