543. 二叉树的直径（Diameter of Binary Tree）
难度：简单 | 主题：二叉树、DFS、后序遍历
题目
给定一棵二叉树，计算它的直径长度。二叉树的直径是任意两个节点路径长度的最大值（边数）。这条路径可能穿过也可能不穿过根节点。
示例
输入：root = [1,2,3,4,5]
输出：3
解释：路径 4→2→1→3 或 5→2→1→3，长度 3
思路
先讲个故事：城市间的公路
想象你在规划一条横跨多个城市的公路，公路只能沿树形结构修建（每个城市最多连到下一个城市）。你要找最长的直达公路——可以穿过任意城市（节点），但不能分叉。
你会发现：最长公路的最高点一定是某个城市，公路从这个城市向左延伸一段、向右延伸一段。公路长度 = 向左的段数 + 向右的段数。
所以问题转化为：对每个节点，计算左右子树的最大深度之和，取全局最大值。
引导式推导：从最大深度到直径
第 1 步：最大深度怎么算？
104二叉树的最大深度 告诉我们：
深度 = 1 + max(左子树深度, 右子树深度)
第 2 步：直径和深度的关系
对任意节点，经过它的最长路径 = 左子树深度 + 右子树深度（边数）。
为什么呢？因为最长路径的”拐点”一定在某个节点上，拐点向左走到最深叶子、向右走到最深叶子，中间经过拐点。
① ← 拐点
↙ ↘
② ③ 左深度 2，右深度 1
↙ ↘
④ ⑤
路径 ④→②→①→③：边数 = 左深度 2 + 右深度 1 = 3
第 3 步：不一定经过根节点
最大直径可能在任意子树内部。所以遍历每个节点时都要尝试更新，不能只看根节点。
第 4 步：后序 DFS 框架
经典套路：「后序 + 全局变量」——递归返回子树深度供父节点用，同时用全局变量记录当前拐点的直径。
和 124二叉树中的最大路径和 完全相同的框架，只不过 124 加的是节点值，这里加的是深度。
代码
def diameterOfBinaryTree(self, root):
self.ans = 1 # 全局最大节点数（直径边数 = 节点数 - 1）
def depth(node):
if not node:
return 0
L = depth(node.left) # 后序：左子树深度
R = depth(node.right) # 后序：右子树深度
self.ans = max(self.ans, L + R + 1) # 拐点处更新：路径节点数 = 左深 + 右深 + 1
return max(L, R) + 1 # 返回当前子树高度（供上层继续算深度）
depth(root)
return self.ans - 1 # 边数 = 节点数 - 1
关键理解「返回值 vs 全局更新」：
-
depth()返回子树高度（单边最长），因为父节点只需要知道”你这边最深多少”才能算自己的高度 -
self.ans记录的是路径节点数（两边之和 + 1），因为直径需要两边相加
如果只用返回值不用全局变量，你无法同时”向上报深度”和”向左右两边求和”——这是后序 DFS 的精髓。
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 每个节点访问一次 |
| 空间 | O(h) | 递归栈深度，最坏 O(n)（链），平均 O(log n) |
实战考量
频率分析
出现在：美团/字节/阿里 二叉树后序遍历题中频。30% 的候选人会犯同一个错——只考虑经过根节点的路径。
延伸思考
Q：直径一定要经过根节点吗？
A：不一定。直径的定义是”任意两个节点的最长路径”，如果根节点的一棵子树内部就有很长的路径，完全可能不经过根。所以在每个节点（拐点）都要更新。
Q：为什么 depth 返回的是高度，但更新直径用的是 left + right？
A：因为高度 = 从节点到最远叶子向下的边数。直径 = 经过该节点的最长路径 = 向左走到最深 + 向右走到最深 = left + right。这是两个不同的量：高度是单边的，直径是双边的。
Q：如果要求返回具体的路径节点，不只是长度？
A：需要记录直径两端的叶子节点，然后从根做 DFS 回溯找到它们之间的路径。实践中一般只问长度。
Q：如果树里有负权边呢？
A：那就是 124二叉树中的最大路径和 的思路，但路径和允许”不走两边”（可以只走一边或单节点）。直径是边数计数，不涉及负值。
易错点
-
初始值
ans=1（节点数），不是 0——单节点树节点数为 1，减 1 得 0 边 -
更新直径用
L + R（边数）或L + R + 1（节点数），返回值用max(L, R) + 1 -
和 124 的区别：124 路径和可以只取一边（负值不取），直径必须两边都取（因为是边数计数）
生活类比
找直径 → 找最长公路
想象一个树形城市群，你要找最远两个城市的路程。
在每个城市（节点），记录”向左最远能走多远”和”向右最远能走多远”。
经过这个城市的最长路 = 向左 + 向右。
全局最长路 = 所有城市里这个和的最大值。
把城市比作交通枢纽：每个枢纽只能记住自己单向最远能到哪（返回值），
但全球交通局记录每个枢纽左右最远之和（全局变量）。
相关题目
| 题目 | 关系 |
|---|---|
| 104二叉树的最大深度 | 直径的基础——先会算深度 |
| 124二叉树中的最大路径和 | 完全相同的后序 DFS 框架，值替换深度 |
| 110平衡二叉树 | 同样是后序 + 高度比较 |
→ 返回题单：LeetCode学习路线图 > 五、二叉树
速记卡（面试闪卡）
Q1：一句话讲清「543. 二叉树的直径（Diameter of Binary Tree）」到底是什么？
A：求二叉树任意两节点间最长路径的边数，用后序 DFS 在每个拐点算左右深度和。
Q2：题目：城市间最长公路（diameter of tree） —— 怎么理解？
A：像在树形城市群规划最长直达公路——只能沿树走、不能分叉，可穿过任意城市。答案就是某节点处”向左最远 + 向右最远”的边数，不一定过根。
Q3：思路：后序 DFS + 全局变量（post-order DFS） —— 怎么理解？
A：递归返回单边深度供父节点用，同时用全局变量 ans 记录每个拐点的 左深+右深。像交通枢纽只记单向最远，交通局记左右之和取最大。深度单边、直径双边，别混。
Q4：代码：返回值 vs 全局更新（depth return） —— 怎么理解？
A：depth() 返回 max(L,R)+1（高度），self.ans 记 L+R+1（节点数）。ans 初值 1（单节点），最后返回 ans-1 得边数。复用 124 最大路径和框架，只是把值换成深度。
Q5：复杂度与实战（O(n) time, O(h) space） —— 怎么理解？
A：时间 O(n)（每节点一次），空间 O(h)（递归栈，最坏链 O(n)）。美团字节阿里中频，30% 人错在”只考虑过根的路径”——必须每节点更新。
Q6：核心速记主线有哪些？
-
题目：任意两节点最长路径边数
-
思路：后序 DFS，每拐点算左深+右深（post-order）
-
代码：返回值记高度，全局 ans 记 L+R+1
-
复杂度：时间 O(n)、空间 O(h)
-
实战：别只看过根路径，每节点更新
口诀
A：公路穿城任意连，
左右深度相加算；
每点都作拐点看，
最大直径现眼前。