二叉树最大路径和：向上只交单边，答案可以拐弯
一条路径总有一个最高点。左右都能用的是这个最高点自己；交给父亲的，只能再选左边或右边一条。
后序递归返回「从当前节点向下、只能走一侧的最大和」：gain = val + max(0, 左gain, 右gain)，负贡献截成 0。节点做折点时的候选是 左gain + val + 右gain，用来更新全局 best。返回给父亲的仍是单边 gain。时间 O(n)，空间 O(h)。
这是 LeetCode 124. Binary Tree Maximum Path Sum。路径定义为树上任意一条不重复走节点的通路，可以不经过根，也可以在某个节点同时走左子树和右子树。求所有路径里节点值之和的最大值。节点值可为负。
小例子 [1,2,3] 的答案是 6，路径 2−1−3。主例层序 [-10, 9, 20, null, null, 15, 7]：根 −10，左叶 9，右子 20，20 再挂 15 和 7。答案是 15−20−7 = 42，不经过根。
把「经过根的那条」当答案会在主例上得到 9+(−10)+20+15=34，小于 42。缺的是两本账：每个节点作为路径最高点时可以左右都要；同一个节点被父亲继续往上接时，只能交出左右里更好的一侧。
只向上传「单边」
任意一条路径有且只有一个最靠近根的节点，叫做折点。折点可以同时接左臂和右臂；折点以上不再往上走。因此，当父亲问「你能给我多长一段」时，你不能把左右两臂都交上去——那样父亲再往另一侧接，路径就会在你这里分叉两次，不再是一条路。
向上的合同是单边最大贡献：先递归左右孩子，得到他们各自的单边 gain，负数用 0 代替（带上它不如在此断开），然后 gain(自己) = val + max(左, 右)。叶子没有孩子，gain 就是自己的值；若叶子是负数，父亲那一层的 max(0, …) 会把它丢掉。
截断看的是孩子的贡献，不是禁止路径出现负数节点。自己的 val 始终加进 gain 和折点候选——题目保证至少选一个节点，全负时答案是最大的那个负节点。
截断max(0, 孩子gain) 的意思是：这条臂交给我当折点或再往上交时，负臂不如不要。主例的 −10 做折点时左臂 9 仍是正的，必须留下。
折点处拼合两边
节点当折点时，经过它的最好路径是 左臂 + 自己 + 右臂，两臂都已经截过负。用这个候选去挑战全局 best。然后仍把单边 gain 返回给父亲。best 和返回值必须分开记：主例 20 的折点候选是 42，向上只能交 20+max(15,7)=35。
后序保证算 20 之前 15、7 已经算完。15、7、9 都是叶子，gain 等于自己。20 做折点：15+20+7=42，best 写成 42，演示第一帧。根 −10 做折点：左臂 max(0,9)=9，右臂 max(0,35)=35，候选 9+(−10)+35=34，打不过 42。向上交 −10+35=25，没人再要。答案停在 42。
best 必须初始化成极小值，不能垫 0：全是负数时 0 不是一条合法路径。每个节点恰好当一次折点、交一次单边，整棵树走一遍。
Go：后序 + 全局最大
func maxPathSum(root *TreeNode) int {best := math.MinIntvar gain func(*TreeNode) intgain = func(n *TreeNode) int {if n == nil { return 0 }l := max(0, gain(n.Left))r := max(0, gain(n.Right))best = max(best, l+n.Val+r)return n.Val + max(l, r)}gain(root)return best}
1best 垫成 MinInt。全负树的答案是最大的负节点，垫 0 会错。
2空孩子返回 0，再被 max(0, …) 吃掉，等于没有这臂。
3l、r 已是非负臂长。l+n.Val+r 是「在这里拐弯」的候选。主例 20 处写成 42。
4return 只加左右里更大的一侧。20 交 35，不是 42；父亲若把 42 当右臂，会把 15 和 7 同时接进一条向上的路。
总结
折点可以左右都要，向上只能交单边；负臂截成 0。主例答案 42，不经过 −10。
- 把经过根的路径当答案，主例最多 34，小于 15−20−7。
- gain 和 best 是两本账。20 的 42 只进 best，交上去的是 35。
- 与 LC543 同构：那里折点拼的是边数，这里拼的是权值和。