LC124　二叉树中的最大路径和¶

困难通过率 48.3%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索动态规划二叉树树形 DP

讲解章节：树形 DP

一句话

每个节点算一次「左右两条下行链在此汇合」，取全局最大。

解题思路¶

这题考什么¶

路径是一条不重复经过节点的节点序列，可以拐弯，也不必经过根。逐条枚举显然不可行，要抓住路径的结构：任何一条路径放回树里看，一定有唯一一个最高点（离根最近的那个节点）。以最高点为界，路径被拆成两条从它出发往下走的链（其中一条可以为空）。

于是把「枚举路径」换成「枚举最高点」：对每个节点 node 只问一件事 —— 以它为最高点的最大路径和是多少？答案是

node.val + 左子树能向上贡献的最大值 + 右子树能向上贡献的最大值

这里的「向上贡献」指一条单边下行链的最大和（不能拐弯，拐过弯的路径没法再往上接）。记作 up(node)：

up(node) = max(node.val + max(up(左), up(右)), 0)

最外层那个 max(..., 0) 是全部精髓：节点值可以是负的，一支贡献为负的链不如干脆不接，截成 0 就表示放弃它。这是典型的树形动态规划（树形 DP），同款套路见树的基础与遍历的「树的直径」一节（树形 DP 做法）。

两处 max 的角色不同，别混：算 up 时左右两支只能二选一（链不能拐弯），算答案时左右两支同时取（在 node 处汇合，正好拐一次弯）。

示例 2 的 [-10,9,20,null,null,15,7]：

up(9) = max(9, 0) = 9，up(15) = 15，up(7) = 7
node = 20：答案候选 20 + 15 + 7 = 42；up(20) = max(20 + 15, 0) = 35
node = -10：答案候选 -10 + 9 + 35 = 34，不敌 42

返回 42，与样例一致。

数据规模与复杂度¶

节点数在 [1, 3 * 10^4]，节点值在 [-1000, 1000]。每个节点被展开一次、结算一次，时间 O(n)；栈与记录表都是 O(n)（栈深不超过树高，链状树就是 n）。

坑在哪¶

必须迭代。n 到 3e4，最坏是一条链，递归深度 3e4，远超 CPython 默认的 1000 层上限，递归版直接 RecursionError；递归改迭代见 DFS 深度优先搜索的 60.4 节。这里用「进出两次」的后序遍历：第一次弹出只负责把自己和两个孩子重新压栈，第二次弹出时孩子都已结算完，可以安全取用它们的 up 值。
答案初值不能取 0。全负的树（例如单节点 [-3]）的最大路径和就是 -3，取 0 会错报成 0。这里拿 root.val 起头，它本身就是一条合法路径的和。
负贡献要截成 0，但节点自身的值不能截。up 里截零表示「不接这一支」，而以 node 为最高点的路径必定包含 node，所以 node.val 原样加上。
向上传的是单边链，不是拐过弯的路径。up 里对左右取 max 而不是相加；写成相加就等于把一条已经拐过弯的路径再往上接，路径会重复经过 node。
记录表用节点的 id 当键。TreeNode 没有自定义相等与哈希，拿对象本身当键与拿 id 当键完全等价，写成 id 只是把「比的是同一个节点」讲明白；空孩子查不到，get 的默认值 0 正好就是「这一支不接」。

参考实现¶

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


class Solution:
    def maxPathSum(self, root: "Optional[TreeNode]") -> int:
        # 题面保证至少一个节点。用根的值起头，答案初值本身就是一条合法路径的和，
        # 全负的树才不会被 0 顶掉
        best = root.val
        # id(节点) -> up 值：以该节点为顶端、只往下走一条链的最大和，已经截成非负
        up = {}
        # 栈元素是 (节点, 是否已展开)。False 表示还没安排孩子，
        # True 表示两个孩子都结算完了、轮到自己 —— 这就是后序遍历的迭代写法
        stack = [(root, False)]
        while stack:
            node, expanded = stack.pop()
            # 空孩子照压不误，弹出时统一跳过，压栈处就不必逐个判空
            if node is None:
                continue
            if not expanded:
                # 先把自己以 True 压回去，压在两个孩子下面，保证孩子先结算
                stack.append((node, True))
                stack.append((node.left, False))
                stack.append((node.right, False))
                continue
            # 查不到就是空孩子，默认 0 表示「这一支不接」
            left = up.get(id(node.left), 0)
            right = up.get(id(node.right), 0)
            # 以 node 为最高点的路径：左右两条链在此汇合，node 自身必须计入
            best = max(best, node.val + left + right)
            # 往上传的只能是单边链，左右二选一；整体为负就截成 0，表示放弃这一支
            up[id(node)] = max(node.val + max(left, right), 0)
        return best

LC124 二叉树中的最大路径和¶