题目描述
思路解析
一句话答案：LeetCode 124 二叉树中的最大路径和用树形 DP 一趟后序遍历解决：每个节点用 node.val + L + R 这个「穿过自己」的路径和更新全局答案，但返回给父亲的只有单边贡献 node.val + max(L, R)，且孩子的负贡献先用 max(0, …) 裁成 0。时间 O(n)，空间 O(h)。
这道题的路径和直觉里的不一样
这里的「路径」是树中任意一串相邻相连的节点：不必经过根、不必到叶子、可以在某个节点处拐弯（一头来自左子树、一头来自右子树），但不能分叉成三条。节点值可正可负，路径至少含一个节点。要求所有合法路径里节点值之和的最大值。「可负」和「不必过根」这两点，决定了它比求直径（LeetCode 543）多一层裁剪逻辑。
为什么按最高拐点枚举就不重不漏
路径的形状有个不变的骨架：任何一条路径都存在唯一一个位置最高的节点，路径在它这里拐弯，两头分别沿左、右子树往下延伸（某一头可以为空）。于是把所有路径按「最高拐点是谁」分类——每个节点当一次拐点，算出以它为拐点能拼出的最大路径和，取全局最大，就必然覆盖所有路径且互不重复。以节点 x 为拐点的最优值是 x.val + L + R，其中 L、R 分别是左右孩子往下延伸的最大单边和。这类在树上自底向上递推的做法通常叫树形 DP。
为什么返回给父亲的是单边而不是左加右
递归函数 gain(node) 要给父亲一个数：从父亲走进 node 之后，往下最多还能捞多少分。路径进了 node 只能继续沿一条腿往下走——若左右都走就在 node 处拐了弯，而拐点已经是 node，这条路径不可能再向上延伸到父亲。所以返回值只能是 node.val + max(L, R)，即挑更肥的那条腿。
而 node.val + L + R 是把两条腿都接上的「拐弯路径」，它是 node 作为拐点的完整答案，只能就地和全局最大值比较，不能上传。一个函数、两个口径——返回单边、全局收拐弯值——是这套套路的核心，混用任何一个都错。
负贡献为什么要裁成零
路径有权「不要」某条子分支：如果一条腿往下走的最大和是负数，接上它只会拖累总和，最优选择就是不走这条腿，等价于让它贡献 0。所以代码里读孩子返回值时先做 L = max(0, gain(node.left))、R 同理。这一步是本题与求直径最大的差别——直径里边数不会为负，不需要裁剪；本题节点值可负，不裁剪就会把明明可以舍弃的负分强行算进来。
答案初值为什么必须是负无穷
全局答案 ans 的初值要设成负无穷而不是 0。因为路径至少要含一个节点，当整棵树全是负数时（比如只有一个值为 -3 的节点），正确答案是 -3；初值若是 0，它比任何真实路径和都大，会错误地输出 0。设成负无穷后，每个节点的拐弯值 node.val + L + R 至少会以「只含自己」的形式参与一次比较（此时 L、R 被裁成 0），全负树也能得到正确的最大单点值。
复杂度与同构题
时间 O(n)：后序遍历中每个节点恰好访问一次，每次只做常数次比较与加法。空间 O(h)：递归栈深度等于树高，最坏退化成链是 O(n)。
「返回单边链、全局更新拼接值」这套骨架能直接套到一批题上：二叉树的直径（LeetCode 543）是边数版，最长同值路径（LeetCode 687）是加约束版；本题是在骨架上叠加 max(0, …) 处理负值。骨架吃透，这一族题只剩口径差异。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住：返回给父亲的值（单边贡献）和更新答案用的值（左+右穿过值）不是同一个数；而且负贡献都要先裁成 0——这是本题比「求直径」多出来的一步。
后序遍历：先把左子树彻底算完，再右子树，最后才轮到父亲。每个节点会留下记录：返回给父亲的「单边贡献」、穿过自己的「路径和」，以及当前的全局最大答案。
轮到节点 9（橙色）。它是叶子，左右孩子都空 → 左贡献 = 0、右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 9 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 9 + 0 + 0 = 9（刷新了全局最大 → 9）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 9 + max(0, 0) = 9——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 7（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 9 → max(0, 9) = 9；右孩子为空 → 右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 7 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 7 + 9 + 0 = 16（刷新了全局最大 → 16）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 7 + max(9, 0) = 16——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 2（橙色）。它是叶子，左右孩子都空 → 左贡献 = 0、右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 2 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 2 + 0 + 0 = 2（没超过当前最大 16）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 2 + max(0, 0) = 2——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 11（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 16 → max(0, 16) = 16；右孩子返回 2 → max(0, 2) = 2。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 11 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 11 + 16 + 2 = 29（刷新了全局最大 → 29）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 11 + max(16, 2) = 27——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 -6（橙色）。它是叶子，左右孩子都空 → 左贡献 = 0、右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 -6 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = -6 + 0 + 0 = -6（没超过当前最大 29）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = -6 + max(0, 0) = -6——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 4（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 27 → max(0, 27) = 27；右孩子返回 -6 → 是负的，max(0, -6) 裁成 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 4 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 4 + 27 + 0 = 31（刷新了全局最大 → 31）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 4 + max(27, 0) = 31——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 -4（橙色）。它是叶子，左右孩子都空 → 左贡献 = 0、右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 -4 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = -4 + 0 + 0 = -4（没超过当前最大 31）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = -4 + max(0, 0) = -4——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 13（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 -4 → 是负的，max(0, -4) 裁成 0（这条分支宁可不走）；右孩子为空 → 右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 13 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 13 + 0 + 0 = 13（没超过当前最大 31）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 13 + max(0, 0) = 13——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 -1（橙色）。它是叶子，左右孩子都空 → 左贡献 = 0、右贡献 = 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 -1 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = -1 + 0 + 0 = -1（没超过当前最大 31）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = -1 + max(0, 0) = -1——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 8（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 13 → max(0, 13) = 13；右孩子返回 -1 → 是负的，max(0, -1) 裁成 0。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 8 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 8 + 13 + 0 = 21（没超过当前最大 31）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 8 + max(13, 0) = 21——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
轮到节点 5（橙色）。先读两个孩子已经返回好的单边贡献，并各做一次 max(0, …) 裁剪：左孩子返回 31 → max(0, 31) = 31；右孩子返回 21 → max(0, 21) = 21。 这两个贡献都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 5 算完（转绿）。① 穿过它的路径和 = 节点值 + 左贡献 + 右贡献 = 5 + 31 + 21 = 57（刷新了全局最大 → 57）。② 返回给父亲的单边贡献 = 节点值 + max(左贡献, 右贡献) = 5 + max(31, 21) = 36——注意这两个数不同：返回的只挑一条腿（单边），更新答案用的是左右两条腿一起拼。
全部算完。所有节点里最大的「穿过值」出现在拐点节点 5 上，等于 57。绿色加亮的就是这条最大路径——它在节点 5 处把左右两条「贡献为正」的最深链拼起来；那些负贡献的分支（被 max(0,…) 裁掉的）一律没被选进路径。这说明答案要靠「每个节点各算一次 val+左+右」逐个比较，而不是看某一条到底的链。
单负节点、退化链都被这套递归天然覆盖；关键是 ans 用负无穷起步，单边贡献用 max(0,…) 兜底。
认出这个「返回单边、全局拼接、负的裁零」的模板，一类树形 DP 题就通了。
参考代码
class Solution: def maxPathSum(self, root): self.ans = float("-inf") def gain(node): if not node: return 0 L = max(0, gain(node.left)) # 负贡献裁成 0 R = max(0, gain(node.right)) self.ans = max(self.ans, node.val + L + R) # 穿过本节点 return node.val + max(L, R) # 返回单边贡献 gain(root) return self.ans复杂度
- 时间：O(n)，每个节点只在后序里访问一次
- 空间：O(h)，递归栈深度 = 树高 h，最坏（退化成链）O(n)
易错点
面试追问把动画讲成自己的话
追问为什么左右贡献要 max(0, …)？
追问为什么返回给父亲的是 max(L,R) 而不是 L+R？
追问这套「递归返回单边、全局更新拐弯值」的套路还能解什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的序列化与反序列化
LeetCode 297 · 困难 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题