题目描述
求任意两节点路径长度(边数)的最大值。这条路不一定经过根。
思路解析
最直接的想法：枚举每个节点当「拐点」，再分别 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)、最长同值路径都是这个套路。
参考代码（Python）
1self.diam = 0
2def depth(node):
3 if not node: return 0 # 空树深度 0
4 L = depth(node.left) # 先拿左深
5 R = depth(node.right) # 再拿右深
6 self.diam = max(self.diam, L + R) # 穿过它的路，结算全局
7 return 1 + max(L, R) # 返回深度给父亲
8depth(root); return self.diam复杂度分析
- 时间复杂度：O(n) —— 一次后序遍历
- 空间复杂度：O(h) —— 递归栈
套路模板
记住这个骨架：全局变量在当前节点“结算横跨路径”，返回值给父节点“向上延伸”。分清这两者，这类题就不容易出错。
1self.ans = 初值
2def dfs(node):
3 if not node: return 0
4 L, R = dfs(node.left), dfs(node.right)
5 self.ans = max(self.ans, 用 L,R 在此结算) # 经过当前点的答案
6 return 能向上拼接的量(L, R, node) # 给父亲用易错点
- 错误写法：返回 L+R 给父亲 → 正确写法：返回 1+max(L,R)（给父亲的是深度(只能选一条边往上)，不是横跨路径）
- 错误写法：直径按节点数算 → 正确写法：直径是边数 = L+R（深度按节点、直径按边，差一要分清）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。