LeetCode 124. 二叉树中的最大路径和：树形 DP 的进阶一课

二叉树中的最大路径和（LeetCode 124，Hard）是树形 DP 的进阶一课。本库《最近公共祖先》讲过树形递归的第一课，那一课的递归「返回值」就是「答案」；这一课的核心难点是：路径的定义变宽了——路径可以从树上任意节点出发、到任意节点结束，可以「从左子树上来、穿过根、再下到右子树」——这种「穿过」的形态，让「递归返回值」没法直接当答案用。破解的钥匙是一个拆分动作：把「向上的贡献」与「全局的最优」拆成两个东西。

关键拆分：递归返回「单链」，答案在「分叉点」更新

先把路径形态分类。经过某个节点的最大路径只有三种可能：只有该节点自己；该节点 + 左子树延伸下来的一段；该节点 + 右子树延伸下来的一段；或者该节点 + 左边一段 + 右边一段（节点是路径的「最高点」，左右各挂一段——这就是「穿过」形态）。前三种的共同特征是它们还能继续向上延伸（父节点可以接上「以我为端点的链」）；第四种（穿过）无法再向上延伸（路径已经有了左右两个分支，不可能再分叉）。

于是设计：递归函数 gain(node) 返回「以 node 为端点、向下延伸的单链最大贡献」——它只能选三样：自己自己（node.val）、自己+左链、自己+右链，取最大；注意还可以什么都不选（左右链贡献为负时不接），所以每侧与 0 取 max。全局答案 ans 在递归过程中同步更新：每访问一个节点，用它作为「最高点」的完整路径（node.val + max(0,左) + max(0,右)）去更新 ans。两者的关系：gain 是「可向上传递的部分」，ans 是「在所有分叉点取过的全局最大」——递归返回单链，答案全局更新，这十个字是树形 DP 的通用心法。

class Solution:
    def max_path_sum(self, root) -> int:
        self.ans = float("-inf")

        def gain(node) -> int:
            if not node:
                return 0
            left = max(gain(node.left), 0)    # 负贡献不接
            right = max(gain(node.right), 0)
            self.ans = max(self.ans,          # 以 node 为最高点的完整路径
                           node.val + left + right)
            return node.val + max(left, right)  # 向上只能带一条链

        gain(root)
        return self.ans

每个节点访问一次，时间 O(n)、空间 O(h)（递归栈）。

两个关键细节：负贡献的剪枝与负值全树

细节一：与 0 取 max 的含义是「剪枝」——左子树的单链贡献是负数时，接上它只会拖累路径，等效于「不接」（路径从 node 开始）。这个 max(0, ·) 是正确性的关键之一：它同时服务于 gain（向上带不带这条链）与 ans（分叉点接不接）。细节二：全负树的正确性。树全是负数时（如 [-3]），答案应是 -3（路径必须至少含一个节点）——检查代码：gain 对叶节点返回 node.val（必须含自己，不能返回 0——返回 0 意味着「空路径」），ans 初始化为负无穷、由每个节点的「最高点路径」更新——单节点树的 ans 被 -3 + 0 + 0 更新为 -3，正确。「路径至少一个节点」这条题目约束，是很多错误实现的翻车点（把「可以不选」错误地泛化成了「可以空路径」）。测试建议（本地跑通纪律）：全负树、单节点、正负混合的「分叉最优」用例、以及链状树（退化成数组的 Kadane）。

树形 DP 的通用心法与延伸

「返回单链、答案全局」的心法可以迁移到一整类树形问题。同构问题：二叉树的直径（最长路径的「边数」版——同样的分叉结构，把节点和换成边数）、二叉树中的最大路径和的变体（节点带负权、边带权）、以及「监控二叉树」类的状态型树形 DP（每个节点维护多种状态取最优——状态数增多，但「返回子树状态、全局更新答案」的骨架不变）。延伸的心法升级：当树的形态从二叉到多叉、当依赖从「父子」扩展到「节点间的选择约束」（如「相邻节点不能同时选」——打家劫舍 III），递归返回的就不是一个数而是一个状态向量（每个节点返回「选/不选」两种状态的最优值）——树形 DP 的进阶形态。但无论状态多复杂，本篇确立的原则不变：先分清「向上传递的」与「只在局部使用的」，别让「穿过的路径」污染「向上的链」。

手动模拟：负权与「剪枝」的一次完整推演

用一个「负贡献」的例子完整推演，验证 max(0, ·) 的必要性。树结构：根 A(val=5)，左子 B(val=-8)，右子 C(val=3)；B 挂两个叶子 B1(val=-2), B2(val=4)。自底向上推演：B1 是叶 → gain(B1)=−2；B2 是叶 → gain(B2)=4。处理 B：left = max(−2, 0) = 0（B1 的贡献为负，剪掉——路径不从 B1 那边来）；right = max(4, 0) = 4；ans 更新：以 B 为最高点的路径 = −8 + 0 + 4 = −4，不更新全局最优（初始负无穷后已被更大值覆盖——等等，此刻 ans 的历史是：先处理完 B1/B2（叶子不更新 ans 有效的正路径？叶子也更新 ans：gain(叶) 时 ans = max(ans, val+0+0)——B2 的 −2+... 不对，B2 val=4，ans=max(ans, 4)=4）——ans 此刻=4；B 的分叉路径 −4 不更新 ✓。gain(B) = −8 + max(0,4) = −4——B 向上传递的是 −4：A 接不接这条链？ 处理 C：gain(C)=3。处理 A：left = max(gain(B), 0) = max(−4, 0) = 0（A 剪掉了 B 侧的负链！）；right = 3；ans = max(ans, 5+0+3) = 8（A+C 的路径）；gain(A) = 5+3 = 8。最终答案 8 ✓——如果 B 侧没做 max(0,·) 剪枝，A 的路径会被 −4 拖成 4，答案错误。这个推演完整展示了三个要点：叶节点的 val 会参与 ans、负贡献在每一层被 max(0,·) 剪掉、ans 的全局更新与 gain 的单链返回各自独立工作。

「树形 DP + 全局答案」的反面教材：把答案写进返回值的错误

树形 DP 最常见的错误写法值得单独展示：把「全局答案」塞进递归返回值——比如让 gain 返回「以 node 为最高点的完整路径」（node.val + left + right），然后在主函数里 max 所有返回值。这个写法错在哪？「穿过」的路径无法向上传递——父节点接上一个「已经左右分叉」的路径，路径就出现了分叉（不再是合法的单链路径）——返回值的语义被污染，整棵树的递归逻辑随之崩塌；症状通常是「答案偏大」（分叉路径被当作链传递）——偏大的答案比偏小更危险，因为它看起来「合理」。正确的分层再强调一遍：递归返回值只承载「可向上组合的单链贡献」，全局答案用外部变量在「分叉点」独立更新——两层账本、各记各的（本库《打家劫舍 III》的树形 DP 会把这个骨架升级为「状态向量」）。调试技巧：树形 DP 写完先测三个用例——单节点、全负、经典分叉——三个用例过，正确性九成有保障。

同族题地图：直径、路径和、打家劫舍 III 的骨架对比

「返回单链/状态向量、答案全局更新」的树形 DP 骨架，在三个经典题上的形态对比：二叉树的直径（LeetCode 543）——gain 返回「向下深度」（单链的边数版），ans 在每个节点更新「left_depth + right_depth + 0」（穿过根的两条链拼最长）——与本篇同构，路径的「权」从点权和换成边数。二叉树中的最大路径和（本篇）——gain 返回「带权单链（负权可剪）」，ans 更新「点权和 + 左右非负链」。打家劫舍 III（LeetCode 337）——gain 返回状态向量「(偷该节点的最优, 不偷该节点的最优)」两个数，ans 即根节点的 max(偷, 不偷)——它是「返回值从单值升维到向量」的形态（约束是父子不能同偷，所以「不偷」时才能接子节点的「偷」——状态间有依赖）。三题的对比表：返回值的维度（1/1/2）、ans 的更新位置（分叉点/分叉点/根）、约束类型（无/无权剪枝/父子互斥）——树形 DP 的进阶方向就是「返回值向量化」与「状态依赖复杂化」，骨架万年不变。

递归改迭代：树形 DP 的显式栈版本

树形 DP 的递归实现在深层树上会爆栈（Python 默认递归上限 1000——十万节点的链状树直接 RecursionError），改迭代的姿势值得掌握。改法：两遍迭代——第一遍用显式栈做后序遍历的逆（前序遍历入栈、弹出时逆序处理），把节点按「处理顺序」收集；第二遍按收集顺序的逆序处理每个节点的 DP（等价于后序——子节点先于父节点处理）。实现要点：children 的处理顺序与前序的顺序一致（保证处理某节点时其子节点已处理）；状态向量的存取用字典或数组按节点 id 索引。迭代的收益与代价：收益是递归深度风险归零（本库《课程表》的迭代 DFS 同款动机）；代价是代码的抽象度下降（两遍遍历的状态管理比递归啰嗦）。选择的决策：数据规模可预估且浅（面试、小数据）——递归版清晰优先；数据规模不可控（生产、大图）——迭代版稳健优先。这个选择本身，就是「教学代码」与「生产代码」差异的微型标本。

小结

这篇收成四条：路径的「穿过」形态要求拆分——递归返回「以节点为端点的单链贡献」，全局答案在「每个节点作为最高点」时同步更新；单链贡献与 0 取 max 是负贡献的剪枝，同时服务于向上传递与分叉统计；「路径至少含一个节点」的约束靠「叶节点返回自身值、ans 初始负无穷」保证，全负树是必测用例；「返回单链、答案全局」是树形 DP 的通用心法——从直径到打家劫舍 III，变的是状态向量，不变的是骨架。树形递归第一课（最近公共祖先）教的是「后序遍历的返回值」，这一课教的是「返回值与答案的分离」——两课合上，树形 DP 的地基就打完了。

参考资料

LeetCode 124. Binary Tree Maximum Path Sum —— 题目与官方题解
本库前篇：《LeetCode 236. 最近公共祖先：树形递归的第一课》《LeetCode 198. 打家劫舍》
LeetCode 543. 二叉树的直径 —— 「返回单链、答案全局」的入门同构题