力扣HOT100(45) 二叉树的直径
任意一条路径，都可以看作是以某个节点为 “拐点”，左边接左子树的最深路径，右边接右子树的最深路径。
比如路径4→2→1→3的拐点是节点 1：
- 左子树最深路径：
1→2→4（2 条边） - 右子树最深路径：
1→3（1 条边） - 总路径长度：
2+1=3（边数）
所以我们的目标转化为：
- 遍历树中所有节点，计算每个节点作为 “拐点” 时的路径长度；
- 取所有路径长度的最大值，就是整棵树的直径
完整解题步骤
1. 定义两个核心变量
depth(node)：递归函数，返回以node为根的子树的深度（节点数）ans：全局变量，记录所有节点作为拐点时，路径经过的节点数最大值
2. 递归函数depth(node)的逻辑
- 终止条件：如果
node是空节点，返回 0（空树深度为 0） - 递归左子树：得到左子树深度
L - 递归右子树：得到右子树深度
R - 更新最大值：当前节点作为拐点的路径节点数 =
L + R + 1（+1 是加上当前节点本身），用这个值更新ans - 返回当前子树深度：
max(L, R) + 1（当前节点 + 左右子树中更深的那个）
3. 主函数逻辑
- 初始化
ans = 1（至少有一个节点，路径节点数为 1） - 调用
depth(root)遍历整棵树 - 最终直径 =
ans - 1（因为边数 = 节点数 - 1）
class Solution { int ans; // 全局变量：记录所有路径的节点数最大值 // 递归函数：返回以rt为根的子树的深度（节点数） int depth(TreeNode* rt){ // 1. 终止条件：空节点，深度为0 if (rt == NULL) { return 0; } // 2. 先算左子树深度 int L = depth(rt->left); // 3. 再算右子树深度 int R = depth(rt->right); // 4. 关键：计算当前节点作为拐点的路径节点数，更新最大值 ans = max(ans, L + R + 1); // 5. 返回当前子树的深度：左右子树中更深的那个 + 当前节点 return max(L, R) + 1; } public: int diameterOfBinaryTree(TreeNode* root) { ans = 1; // 初始化为1，对应只有一个节点的情况 depth(root); // 遍历整棵树 return ans - 1; // 节点数最大值减1，得到边数（直径） } };