第5章｜二叉树与递归
Unit 06 · LeetCode #543 二叉树的直径
向父节点只返回一条路，
在当前节点计算两条路。
直径可能在任意节点完成转向。递归返回值必须保持为父节点还能继续延伸的单支高度；左右两支拼接得到的路径只能更新全局最优，不能直接向上返回。
外层搜索回答“哪里存在”，内层验证回答“当前候选是否成立”。
返回值供父节点继续组合；局部候选用于更新整棵树的全局答案。
题目要求
给定二叉树根节点 root，返回树中任意两个节点之间最长路径的长度。该路径不一定经过整棵树的根节点。
- 树中节点数为
[1, 10⁴]； - 路径长度按边数计算。
示例与方法
输出：3
输出：1
后序 DFS：每个节点得到左右深度，使用 left_depth + right_depth 更新直径，再返回 1 + max(left_depth, right_depth)。时间 O(n)，递归栈 O(h)。
从当前节点向下，只选择左、右中的一侧，到最远叶子的路径。
在当前节点连接左侧最长单支与右侧最长单支，长度为 L＋R。
先获得左右子树结果，再在当前节点组合并返回。
保存所有已处理节点产生的候选直径最大值。
只能保留一侧，供父节点继续延伸。
允许连接两侧，但只能更新全局答案。
节点高度与候选直径
调用栈
返回值不变量
depth(node) 始终是一条可继续向父节点延伸的单支路径。
全局答案不变量
diameter 保存所有已处理节点中最大的 L + R。
这条路径已经在当前节点分叉。父节点只能通过一条边进入当前节点，不可能同时沿左右两支继续延伸。
1 + max(left_depth, right_depth)
保持为一条单支路径。
max(diameter, left_depth + right_depth)
允许在当前节点连接两支。
把已经分叉的路径交给父节点，破坏返回值形状。
最长路径的转折点可能位于任意内部节点。
迁移目标：LeetCode #124 二叉树中的最大路径和
复用“单支返回＋双支更新全局最优”的结构。唯一关键变化是：状态从边数改为节点值贡献，并且负贡献分支应舍弃。
LeetCode #124｜二叉树中的最大路径和
迁移原题
路径由一系列相邻节点组成，每个节点最多出现一次。路径不一定经过根节点。返回任意非空路径的最大节点值之和。
示例与新增约束
输出：42
输出：6
负分支会降低路径和，因此贡献使用 max(gain(child), 0)。
复用结构，而不是复用数值公式
返回一条单支高度；当前节点连接左右两支更新全局直径。
返回一条单支最大贡献；当前节点连接左右正贡献更新全局路径和。
在 #124 中，gain(node) 应向父节点返回什么？
为什么负贡献必须截断为 0？
例如左分支贡献为 -5，会主动降低当前路径总和。
等价于“不选择该分支”，路径仍可只经过当前节点或另一侧。
当前节点值 20，左贡献 -3，右贡献 7。当前候选路径和是多少？
只补充 #124 相比 #543 的变化槽位
真实轨迹：节点 20 接收 15 与 7 的正贡献
完成 LeetCode 提交代码
继续按钮将在短暂停留后开放，页面不会自动跳转。