题目描述：
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
解题思路：
方法一：递归法（后序遍历）
核心思路：
对于任意节点，经过它的最长路径 = 左子树深度 + 右子树深度
直径 = max(左子树深度 + 右子树深度)
注意：
-
深度是节点数，边数 = 节点数 – 1
-
但 左深度 + 右深度 正好等于边数（因为左右各一条边连接到当前节点）
具体过程示例：
1
/ \\
2 3
/ \\
4 5
节点1: 左深度=2, 右深度=1 → 路径=2+1=3
节点2: 左深度=1, 右深度=1 → 路径=1+1=2
节点4: 左深度=0, 右深度=0 → 路径=0+0=0
节点5: 左深度=0, 右深度=0 → 路径=0+0=0
节点3: 左深度=0, 右深度=0 → 路径=0+0=0
最大直径 = 3 ✅
代码实现：
class Solution {
public:
int diameter = 0; // 全局变量记录最大直径
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return diameter;
}
private:
int depth(TreeNode* node) {
if (node == nullptr) return 0;
int leftDepth = depth(node->left);
int rightDepth = depth(node->right);
// 更新最大直径：经过当前节点的路径
diameter = max(diameter, leftDepth + rightDepth);
// 返回当前节点的深度
return max(leftDepth, rightDepth) + 1;
}
};
复杂度分析：
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(h) | 递归栈深度，h 是树的高度 |
空间复杂度说明：
-
最坏情况（链状树）：O(n)
-
平均情况（平衡树）：O(log n)
关键细节：
1. 为什么 leftDepth + rightDepth 就是边数？
1
/ \\
2 3
/ \\
4 5
节点1的左深度 = 2（路径 1→2→4，边数2）
节点1的右深度 = 1（路径 1→3，边数1）
经过节点1的路径 = 4→2→1→3，边数 = 2+1 = 3
左深度 = 左子树的边数，右深度 = 右子树的边数，加起来就是经过当前节点的总边数。
2. 为什么用全局变量 diameter？
因为最大直径不一定经过根节点，需要遍历所有节点，取最大值。
-
depth 函数返回的是深度（用于上层计算）
-
diameter 记录的是全局最大直径
3. 和「最大深度」的区别
| 104. 最大深度 | 返回 max(left, right) + 1 |
| 543. 直径 | 额外更新 diameter = max(diameter, left + right) |
543 题在 104 题的基础上，多了一步更新直径。
方法二：迭代法（不推荐）
用栈模拟后序遍历，记录每个节点的深度和直径。代码复杂，不推荐。
两种方法对比：
| 递归（后序） | O(n) | O(h) | 简单 | ⭐⭐⭐⭐⭐ |
| 迭代（栈） | O(n) | O(n) | 复杂 | ⭐⭐ |
总结：
| 核心思想 | 经过节点的路径 = 左深度 + 右深度 |
| 递归公式 | diameter = max(diameter, left + right) |
| 返回值 | max(left, right) + 1（深度） |
| 时间复杂度 | O(n) |
| 空间复杂度 | O(h) |
