力扣HOT100(45) 二叉树的直径

任意一条路径，都可以看作是以某个节点为 “拐点”，左边接左子树的最深路径，右边接右子树的最深路径。

比如路径4→2→1→3的拐点是节点 1：

• 左子树最深路径：1→2→4（2 条边）
• 右子树最深路径：1→3（1 条边）
• 总路径长度：2+1=3（边数）

所以我们的目标转化为：

1. 遍历树中所有节点，计算每个节点作为 “拐点” 时的路径长度；
2. 取所有路径长度的最大值，就是整棵树的直径

完整解题步骤

1. 定义两个核心变量

• depth(node)：递归函数，返回以node为根的子树的深度（节点数）
• ans：全局变量，记录所有节点作为拐点时，路径经过的节点数最大值

2. 递归函数depth(node)的逻辑

1. 终止条件：如果node是空节点，返回 0（空树深度为 0）
2. 递归左子树：得到左子树深度L
3. 递归右子树：得到右子树深度R
4. 更新最大值：当前节点作为拐点的路径节点数 =L + R + 1（+1 是加上当前节点本身），用这个值更新ans
5. 返回当前子树深度：max(L, R) + 1（当前节点 + 左右子树中更深的那个）

3. 主函数逻辑

1. 初始化ans = 1（至少有一个节点，路径节点数为 1）
2. 调用depth(root)遍历整棵树
3. 最终直径 =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，得到边数（直径） } };