第5章｜二叉树与递归
Unit 07 · LeetCode #124 二叉树中的最大路径和
负分支先舍弃，
完整路径在当前节点结算。
最大路径和延续 Unit 06 的“双通道递归”：向父节点返回一条可继续延伸的单支增益，在当前节点连接左右两支更新全局最优。新增难点是节点值可能为负，任何负贡献都应视为 0，不被强制接入路径。
返回单支高度；在当前节点使用左右高度之和更新全局直径。
返回单支增益；在当前节点连接左右非负贡献更新全局最大和。
题目要求
给定二叉树根节点 root，返回任意非空路径能够获得的最大节点值之和。路径可以从任意节点开始和结束，不一定经过根节点，同一节点最多出现一次。
- 树中节点数为
[1, 3 × 10⁴]； -1000 ≤ Node.val ≤ 1000。
示例与方法
输出：42
最优路径：15 → 20 → 7
输出：6
后序 DFS：左右子树返回单支增益并与 0 取最大值；当前节点使用 node.val + left_gain + right_gain 更新全局最优，再返回 node.val + max(left_gain, right_gain)。时间 O(n)，递归栈 O(h)。
必须从当前节点出发，只向下选择一侧，可继续交给父节点连接。
max(gain(child), 0) 等价于负分支不参与当前路径。
当前节点同时连接左右非负贡献，得到一次完整路径结算。
best 必须从负无穷开始，才能正确处理全负数树。
只能保留一侧，供父节点继续连接。
允许连接两侧，但只能更新全局 best。
节点增益与候选路径和
调用栈
返回值不变量
gain(node) 始终是一条从当前节点出发、可继续向父节点延伸的最大单支路径和。
全局答案不变量
best 保存所有已处理区域中的最大非空路径和。
负贡献应按 0 舍弃；左右两支组成的完整路径已经在当前节点转向，只能更新全局最优，不能再作为单支增益向父节点返回。
node.val + max(left_gain, right_gain)
保持为一条单支路径。
max(best, node.val + left_gain + right_gain)
允许在当前节点连接两支。
负增益会降低所有经过父节点的候选路径和。
全负数树会被错误解释成允许选择空路径。
迁移目标：LeetCode #687 最长同值路径
继续复用“单支返回＋双支更新全局最优”。变化是贡献重新按边数计算，并且一条边只有在父子节点值相同时才可延伸。
LeetCode #687｜最长同值路径
迁移原题
给定二叉树根节点 root，返回树中最长的、路径上每个节点值都相同的路径长度。路径长度按边数计算，且不一定经过根节点。
示例与新增条件
输出：2
输出：2
只有孩子值与当前节点相同，该侧返回边数才能加 1；否则该侧贡献为 0。
复用“双通道”，替换分支可用条件
返回最大单支增益；当前节点连接左右可用贡献更新全局路径和。
返回同值单支边数；当前节点连接左右同值边更新最长路径。
arrow(node) 应向父节点返回什么？
边是否可延伸，取决于父子节点值
该侧不能接入当前同值路径，贡献直接归零。
该侧贡献为子调用返回值加 1 条连接边。
当前节点值为 5，左孩子值为 4，arrow(left)=3。left_arrow 应是多少？
只补充 #687 相比 #124 的变化槽位
真实轨迹：右侧两个 5 形成可延伸链
完成 LeetCode 提交代码
继续按钮将在短暂停留后开放，页面不会自动跳转。