力扣刷题#31-0543-二叉树的直径
题目
给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。路径长度由它们之间边数表示。
输入: root = [1,2,3,4,5]1/ \2 3/ \4 5
输出: 3
解释: 最长路径是 4→2→1→3 或 5→2→1→3，长度 3（3 条边）
我的思路之旅
第一反应：左子树深度 + 右子树深度？
看到"最长路径"，我第一反应是：左子树跑一遍 DFS 求深度，右子树也跑一遍，相加就是直径。
这个想法对"经过根节点"的路径成立，但题目明确说"可能不经过根节点"——直径可能完全藏在某一侧子树里：
1/ \2 3/ \4 5/ \6 7直径 = 6→4→2→5 这条（藏在左子树内部）
如果只算根的左+右：深度(左子树2)=3，深度(右子树3)=1 → 3+1=4
但真实直径在左子树内部是 6→4→2→5 = 3 条边...
只算根节点会漏掉藏在子树内部的更长路径。
关键洞察：每个节点都可能是"拐点"
任意一条直径路径，一定有一个最高点（路径的转折点）。所以正确答案是：
对每个节点 node：穿过它的最长路径 = node左子树深度 + node右子树深度用这个值更新全局最大值 ansDFS 返回 node 的深度（较深那侧 + 1），供父节点使用
一次 DFS 干两件事：返回深度给父节点 + 顺手用局部路径长度更新全局最大值。
生活化类比：
测量整座山脉的最长山路。不能只看主峰——要从每个山头都出发算一遍"从它这个山脊往左右延伸最长能多远"，取所有山头里最大的那个。
我的 AC 代码
class Solution {
public:int ans = 0;int dfs(TreeNode* root) {if (root == nullptr) return 0;int left = dfs(root->left);int right = dfs(root->right);ans = max(left + right, ans);return max(left, right) + 1;}int diameterOfBinaryTree(TreeNode* root) {dfs(root);return ans;}
};
代码逐段解析
第 3 行：全局变量
int ans = 0;
成员变量，跨越所有递归调用共享。记录"穿过每个节点的最长路径"的最大值。
第 5-6 行：递归出口
if (root == nullptr) return 0;
空节点深度为 0。
第 7-8 行：左右深度
int left = dfs(root->left);
int right = dfs(root->right);
递归拿到左右子树的深度。先信任子树能算出来——这就是递归思维。
第 9 行：更新全局答案
ans = max(left + right, ans);
穿过当前节点的路径 = 左深度 + 右深度。不断和全局最大值比，取更大者。
第 11 行：返回深度
return max(left, right) + 1;
本子树的深度 = 较深那侧 + 1（自己这一层），供父节点继续用。
第 15-17 行：入口
int diameterOfBinaryTree(TreeNode* root) {dfs(root);return ans;
}
调用一次 DFS，期间 ans 被所有节点更新过，最后直接返回。
为什么这个解法能覆盖"不经过根"的情况？
因为 ans = max(left + right, ans) 在每一个节点都会执行一次。
1/ \2 3/ \4 5dfs(4): left=0, right=0 → ans=max(0,0)=0 → return 1
dfs(5): left=0, right=0 → ans=max(0,0)=0 → return 1
dfs(2): left=1, right=1 → ans=max(2,0)=2 → return 2 ← 2 就是路径 4→2→5 的长度
dfs(3): left=0, right=0 → ans=max(0,2)=2 → return 1
dfs(1): left=2, right=1 → ans=max(3,2)=3 → return 3 ← 1 这里更新为 3最终 ans = 3 ✓
无论直径的拐点在哪一层，那个节点的 left+right 都会更新 ans。
复杂度分析
| 维度 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(h) | 递归栈深度 = 树高 |
关键点总结
| 关键点 | 说明 |
|---|---|
| 核心套路 | DFS + 全局变量：一次遍历干两件事 |
| 返回什么 | 子树的深度（max(左,右)+1） |
| 更新什么 | 穿过当前节点的路径长（left+right） |
| 为什么对 | 每个节点都当"拐点"更新一次，覆盖不经过根的路径 |
| 我的弯路 | 只算根的左+右 → 漏掉子树内部更长的路径 |
本文档由 AI 辅助生成，作者提供问题，思路和代码，AI仅负责文本修饰，综合获得以上内容。