二叉树中的最大路径和

关键不是背模板，而是看懂为什么这题适合二叉树 · 树形 DP。

1. 后序先算左贡献：树形 DP 用后序遍历：要先拿到左右子树的结果，才能算当前节点。所以先深入左子树 9，算出它能向上贡献多少。

2. 负贡献不要，直接当 0：拿到子树贡献后先过一道闸：如果是负数，接上它只会让路径和更小，于是用 max(0, 贡献) 直接当 0——相当于这一支不要了。

3. 再算右贡献：同样地深入右子树，算出右边能向上贡献的最大值(同样负的就当 0)。左右贡献都拿到了，才轮到处理当前节点。

4. 穿过当前节点的路径 = 左 + val + 右：先处理右子树的根 20。穿过 20 的路径可以从左拐到 15、再从右拐到 7，所以穿过值 = 15 + 20 + 7 = 42。这是「在 20 这里拐了个弯」的路径。

5. 用穿过值更新全局答案：这个穿过值 42 可能就是最终答案，所以用它去更新全局最大值。注意：它只更新答案，并不往上返回——拐过弯的路不能再接给父亲。

6. 返回给父亲时只能选一边：现在轮到把结果返回给父亲 -10。父亲要把 20 这一支接成一条不分叉的直路，所以 20 只能保留左右里更大的一边，不能左右都要。

7. 返回 val + max(左,右)：于是返回值 = 20 + max(左15, 右7) = 35，把较大的左边 15 接上。穿过值 42 用来更新答案、返回值 35 交给父亲——同一个节点，两个不同的值。

8. 根处理完，全局答案是 42：回到根 -10：左贡献 max(0,9)=9、右贡献 max(0,35)=35，穿过根 = 9+(-10)+35 = 34，没超过 42。所有节点都比过一遍后，全局答案定格在 42，也就是路径 15→20→7。

关键帧 · 一个节点要算「两个值」：这是树形 DP 最难、最容易写错的一帧：每个节点要算两个不同的值。第一个是「穿过它的路径」，可以从左孩子拐上来、再拐到右孩子，等于 15 + 20 + 7 = 42——它能成为答案，因为一条路径允许在某个节点拐一次弯。第二个是「返回给父亲的值」，父亲要把它接成一条直路、不能分叉，所以只能选 20 加上左右里更大的一边 = 35。把这两个值搞混，就是这题最大的坑。

把这句话记住，下次遇到同类题，就能更快选出方向。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：本题边界全在负数：单节点和全负树时，穿过值就是节点自身，所以全局答案初值必须是 -∞、不能是 0。

面试追问：三个高频追问。第一，一个节点为什么算两个值：穿过值更新答案不上交、返回值给父亲只能一条直边。第二，负贡献为什么 max(0)：接负的只会更小，不如不接。第三，它和直径 LC543 是同一套『返回值+全局答案』框架，把深度换成路径和。