Leetcode Hot 100 继续往二叉树深处钻，这次轮到一题名字挺唬人、实则套路很清晰的经典选手：二叉树的直径。
一听“直径”，不少人脑子里会先冒出圆、半径、几何图形， 结果点开题目一看：
哦，原来是树上最长路径。
这题的关键不在“画圆”，而在“算深度”。 你只要把这个弯拐过来，它就从“有点抽象”变成“递归老朋友”。
题目链接
题目描述
给你一棵二叉树的根节点 root，返回这棵树的 直径。
这里的直径指的是任意两个节点之间最长路径的长度。 这个路径不一定经过根节点。
注意，题目中的路径长度按 边数 计算，不是按节点数计算。
解题思路：递归求深度，顺手更新直径
这题表面上是在求整棵树的最长路径， 但递归时最容易下手的，其实不是“路径”，而是：
某个节点往下走，最多能走多深。
也就是子树的最大深度。
为什么先想深度？ 因为如果我们已经知道某个节点：
- 左子树最大深度是
depth_l - 右子树最大深度是
depth_r
那么：
经过当前节点的最长路径长度，就是
depth_l + depth_r。
很像一条路从左边最深处爬上来， 穿过当前节点， 再一路走到右边最深处。
于是整题就变成了两件事同时做：
- 递归返回当前子树的最大深度
- 在每个节点尝试更新整棵树的最大直径
这就属于典型的：
主线求深度，支线刷答案。
代码实现
class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: Optional[TreeNode] :rtype: int """ self.ans = 0
def dfs(node): if node is None: return 0 depth_l, depth_r = dfs(node.left), dfs(node.right) self.ans = max(depth_l + depth_r, self.ans) return max(depth_l, depth_r) + 1
dfs(root) return self.ans代码解析
1. dfs(node) 返回的是什么
很多同学第一次写这题，容易把递归函数的职责搞混。
这里的 dfs(node) 返回的不是直径，
而是：
以
node为根的这棵子树的最大深度。
也就是说，函数要做的是告诉父节点：
- “我这边往下最多还能走几层”
所以最终返回值是：
return max(depth_l, depth_r) + 1含义就是：
- 左右子树谁更深，就沿着谁往上报
- 再加上当前节点这一层
2. 为什么用 self.ans 记录答案
因为这题里有两个不同的信息：
- 递归函数返回给父节点的是“深度”
- 整棵树真正要求的是“最大直径”
这俩不是一回事，不能混在一个返回值里乱炖。
所以最自然的做法就是：
dfs()专心返回深度self.ans专门记录全局最优直径
每递归到一个节点时，都更新一次：
self.ans = max(depth_l + depth_r, self.ans)这表示：
- 把当前节点当作一条路径的“拐点”
- 看看经过它的路径，能不能刷新历史纪录
3. 空节点为什么返回 0
if node is None: return 0因为空节点没有深度，返回 0 非常自然。
这样叶子节点就会得到：
- 左深度
0 - 右深度
0
于是叶子节点向上返回：
max(0, 0) + 1 = 1这表示：
- 以叶子节点为根的子树深度是
1
这个定义和递归过程是完全顺上的。
为什么 depth_l + depth_r 就是直径候选值
设某个节点是路径中间的连接点。 那么一条经过它的最长路径，会长这样：
- 从左子树最深处一路上来
- 经过当前节点
- 再走到右子树最深处
所以边数刚好就是：
depth_l + depth_r注意这里为什么不用再加 1？
因为题目要求的是边数，不是节点数。
如果你脑子里想的是“节点层数”，容易手一抖写成：
depth_l + depth_r + 1那就会多算一个节点，答案直接跑偏。
示例理解
来看经典例子：
1 / \ 2 3 / \ 4 5这棵树的最长路径可以是：
4 -> 2 -> 1 -> 3或者：
5 -> 2 -> 1 -> 3这两条路径的长度都是 3 条边。
当递归来到节点 1 时：
- 左子树最大深度为
2 - 右子树最大深度为
1
于是：
depth_l + depth_r = 2 + 1 = 3这就成功更新了答案。
这题为什么不能只看根节点
这是另一个很容易踩的坑。
很多人会下意识觉得：
直径嘛，最长路径嘛，那大概率经过根节点吧？
不一定，真不一定。
最长路径可能：
- 经过根节点
- 也可能完全藏在左子树里
- 还可能完全藏在右子树里
所以我们不能只在根节点算一次， 而是要在每个节点都尝试更新直径。
这也是为什么全局答案要在整个 DFS 过程中不断刷新。
复杂度分析
时间复杂度
每个节点只会被访问一次，所以时间复杂度是：
O(n)其中 n 是二叉树的节点数。
空间复杂度
递归调用栈的深度取决于树高，因此空间复杂度为：
O(h)其中 h 是树的高度。
- 平衡树情况下约为
O(log n) - 极端情况下退化成链表，则最坏为
O(n)
易错点总结
1. 把直径理解成节点数
题目求的是路径长度，按边数算。
所以当前节点的候选直径是：
depth_l + depth_r不是：
depth_l + depth_r + 12. 以为最长路径一定经过根节点
这题明说了：
路径不一定经过根节点
所以必须在每个节点更新一次答案，不能只盯着根看。
3. 混淆“递归返回值”和“全局答案”
记住这题的分工：
dfs(node)返回深度self.ans记录直径
一个负责向上汇报， 一个负责全场记分。
别让递归既想报深度、又想顺便把直径塞回去， 最后容易把自己绕成毛线球。
小结
这题的核心其实就一句：
某个节点的直径候选值，等于左子树最大深度加右子树最大深度。
所以写法也很经典：
- 递归求左右子树深度
- 顺手更新全局最大直径
- 最后返回深度，答案存在
self.ans里
它本质上是一道“借深度求路径”的递归题。 看着像在问最长路，实际上是在查你会不会一边爬树、一边记账。 树在长，答案也在涨，手法要稳，别被“直径”俩字唬住了。🦐