二叉树中的最大路径和
Binary Tree Maximum Path Sum
返回二叉树中任意路径的最大节点和；路径至少包含一个节点，不要求经过根。
在力扣中练习题目描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
解题思路
主解法
后序 · 单边贡献
每个节点返回一条最优单链，同时用左右贡献更新答案
路径在某个节点处最高：它可以同时向左、向右各延伸一条链。设左子树向上能提供的最大贡献为 left，右子树为 right，那么经过当前节点的最优路径和是 node->val + left + right。
但返回给父节点时，路径不能分叉，只能选左右中更大的一条：node->val + max(left, right)。
分步图解
路径可以在任意节点拐弯；每个节点返回一条能向上延伸的链，best 记录已经出现的最大和。
后序计算单边贡献，同时更新全局最优
如果某条子链的贡献是负数，带上它只会让和变小，所以用 max(gain, 0) 截断。注意这和“路径至少一个节点”不冲突：当前节点本身仍会被计入，best 至少能取到某个单节点。
分步图解
节点 -4：左贡献 2，右贡献 13，经过它的路径和 11；向上返回 9。
负数贡献若不能连接更大的正值，父节点会用 max(...,0) 丢掉它。
- left
- 2
- right
- 13
- best
- 13
后序计算单边贡献，同时更新全局最优
自拟树中 −1 被丢弃，但 −4 被保留：它连接了左侧的 2 和右侧 5/8 的正贡献。最终 8 → 5 → −4 → 6 → 9 → 12 的和是 36。
时间 O(n)，递归深度 O(h)。
时间 O(n)空间 O(h)
易错点
- 向上返回 val + left + right：父节点会拿到一条分叉路径，重复计算。
- 忘记 max(...,0)：负贡献会把更大的正路径拉低。
- best 初始化为 0：全负树会返回 0，但路径必须至少有一个节点。
- 把节点和当成边数：本题累加的是 val，不是路径长度。
代码与演示
演示输入
root = [6,-4,9,2,5,null,12,null,null,-1,8]路径可以在任意节点拐弯；每个节点返回一条能向上延伸的链，best 记录已经出现的最大和。
后序计算单边贡献，同时更新全局最优
查看 C++ 代码
延伸阅读
- 树形 DP 的返回值通常只保留“对父节点有用的一种状态”；分叉的最优值留在全局答案里。
- 本题与直径（543）结构相同：一个返回单边，一个用两边拼接更新全局。