题目概述
给你一棵二叉树的根节点 root，请你返回这棵树的直径。
所谓直径，就是树中任意两个节点之间最长路径的边数。这条路径不一定经过根节点。
示例
输入：root = [1, 2, 3, 4, 5]1/ \2 3/ \4 5输出：3
最长路径是 4 → 2 → 1 → 3，经过了 3 条边，所以直径是 3。
核心思路：求深度的过程中，顺手记录"经过每个节点的最长路径"
这道题乍看和 LC 104（二叉树的最大深度） 好像没什么关系，但其实它的核心代码几乎就是 LC 104 的深度函数，只是多加了一行。
关键观察是：
经过某个节点的最长路径 = 该节点的左子树深度 + 右子树深度。
为什么？因为从左子树最深处出发，经过当前节点，走到右子树最深处，这就是经过这个节点能走出来的最长路径。
所以策略是：
- 写一个递归函数，和 LC 104 一样，计算每个节点的深度
- 在递归过程中，对每个节点都算一下
左深度 + 右深度 - 用一个全局变量
self.ans记录所有节点中左深度 + 右深度的最大值 - 最终
self.ans就是答案
一句话记忆："求深度，记直径"。
代码实现
class Solution:def diameterOfBinaryTree(self, root):self.ans = 0def depth(node):if not node:return 0L = depth(node.left)R = depth(node.right)self.ans = max(self.ans, L + R)return max(L, R) + 1depth(root)return self.ans
逐行拆解
1. 初始化全局记录变量：self.ans = 0
用来在递归过程中记录"见过的最大直径"。初始为 0，因为单个节点的直径是 0。
2. 递归函数签名：depth(node)
这个函数的返回值是以 node 为根的子树的深度（和 LC 104 完全一样）。
但它有一个副作用：每次算出左右深度后，顺手更新 self.ans。
3. 终止条件：if not node: return 0
空节点的深度是 0，这是递归的 base case。
4. 递归求左右深度
L = depth(node.left)
R = depth(node.right)
L 是左子树深度，R 是右子树深度。
5. 更新最大直径：self.ans = max(self.ans, L + R)
这是整道题最关键的一行。
L + R 就是"经过当前节点的最长路径的边数"。为什么是边数而不是节点数？因为左子树深度为 L 意味着从当前节点到左子树最深处有 L 条边，右边同理，加起来就是经过当前节点的路径总边数。
每个节点都算一次，取最大值就是全树的直径。
6. 返回当前节点的深度：return max(L, R) + 1
和 LC 104 一模一样：当前节点的深度 = 左右子树中较深的那个 + 1。
手动模拟
以示例 [1, 2, 3, 4, 5] 为例：
1/ \2 3/ \4 5
递归从根节点 1 开始，但会先一路深入到叶子节点：
depth(4):L = depth(None) = 0R = depth(None) = 0ans = max(0, 0+0) = 0返回 max(0,0)+1 = 1depth(5):L = depth(None) = 0R = depth(None) = 0ans = max(0, 0+0) = 0返回 max(0,0)+1 = 1depth(2):L = depth(4) = 1R = depth(5) = 1ans = max(0, 1+1) = 2 ← 经过节点 2 的路径长度是 2返回 max(1,1)+1 = 2depth(3):L = depth(None) = 0R = depth(None) = 0ans = max(2, 0+0) = 2返回 max(0,0)+1 = 1depth(1):L = depth(2) = 2R = depth(3) = 1ans = max(2, 2+1) = 3 ← 经过节点 1 的路径长度是 3返回 max(2,1)+1 = 3
最终 self.ans = 3，对应路径 4 → 2 → 1 → 3。
复杂度分析
| 复杂度 | 说明 | |
|---|---|---|
| 时间 | O(n) | 每个节点恰好被访问一次 |
| 空间 | O(h) | 递归栈深度等于树的高度 h；最坏情况（链状树）为 O(n)，平衡树为 O(log n) |
总结
| 要点 | 内容 |
|---|---|
| 核心思路 | 经过任意节点的最长路径 = 左子树深度 + 右子树深度 |
| 和 LC 104 的关系 | depth 函数完全一样，只多了一行更新 self.ans |
| 为什么需要全局变量 | 最长路径不一定经过根节点，需要在递归中逐个比较 |
| 一句话记忆 | "求深度，记直径" |
这道题是在 LC 104（最大深度）基础上的经典进阶。它教会我们一个非常实用的递归技巧：递归函数的返回值做一件事，函数体内顺手做另一件事。深度函数返回的是深度，但在计算深度的过程中，我们顺手用 L + R 更新了直径。
掌握了这个"递归中顺手记录全局最优"的模式，后面遇到类似的题（比如二叉树中的最大路径和 LC 124）也会更有思路。