二叉树的直径

最直接的想法：枚举每个节点当「拐点」，再分别 DFS 求它左右子树深度、相加取最大。可每个节点都要重新往下扫一遍，深度被反复重算，整体 O(n²)。

转折点在这：求深度本来就要先拿到左右子树深度——那为什么不在拿到的那一刻顺手算「穿过我的路 = L+R」？一次后序遍历，每个节点深度只算一次：返回给父亲的是深度 1+max(L,R)，同时用全局变量 diam 记下所有 L+R 的最大值。O(n) 搞定。

出发 · 后序先扎到底：后序遍历：先一路递归到最底，再从叶子往上逐个结算。先沿根 1 → 2 往左下扎。全局 diam 初始 0。

叶子 4 · depth=1：到叶子 4：它没有孩子，L=R=0，depth(4)=1+max(0,0)=1。穿过它的路 = 0+0 = 0，diam 不变。把深度 1 返回给父亲 2。

叶子 5 · depth=1：回到 2 再走右孩子 5：同样是叶子，depth(5)=1，穿过它 0，diam 还是 0。返回 1 给 2。（4 已结算，标灰）

节点 2 · 收集左右深：两个孩子都回来了：节点 2 拿到左深 L=1、右深 R=1。现在它手里有了「左右两条最深的腿」，可以结算了。

节点 2 · 结算 + 返回：在 2 这里结算两件事：穿过 2 的路 = L+R = 2（就是 4→2→5），更新 diam=2；但返回给父亲 1 的是深度 = 1+max(1,1)=2（只能挑一条腿往上接）。这两个值不一样，是全题最容易混的地方。

叶子 3 · depth=1：回到根 1，再走右孩子 3：叶子，depth(3)=1，穿过它 0，diam 维持 2。返回 1 给根。

根 1 · 收集左右深：根 1 拿到左深 L=2（来自 2 那一支）、右深 R=1（来自 3）。最后在根这里结算。

根 1 · 结算 → 直径定格：穿过根的路 = L+R = 2+1 = 3，正是 4→2→1→3。更新 diam=3。整棵树后序走完，diam 不再变大，3 就是答案。

这是一类树形题的通用套路：递归返回一个“能拼给父节点”的量（比如深度），同时用全局变量记录一个“在当前节点结算”的答案（比如穿过它的路径）。像最大路径和(124)、最长同值路径都是这个套路。

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

边界三连：二叉树的直径 的边界先看最小规模、空输入和会触发特殊分支的极端样例。

面试追问：二叉树的直径 的追问重点，是把动画里的状态定义、边界和复杂度讲成自己的话。