二叉树的直径 图解题解
最长路径不一定经过根——一次后序遍历，每个节点都当一次候选拐点。
找一棵树里两点之间最远的路，不一定过根。后序遍历到每个节点时，左右子树各能向下延伸的最长边数 L 和 R 都已算好；此刻以该节点为拐点的路径长度恰好是 L+R（边数），用全局变量记下所有候选里的最大值。同时把 1+max(L,R) 往上返给父亲，表示经过我这一侧能再向下延伸多少条边。整棵树只后序走一遍，O(n) 搞定。
这道题到底在问什么
- 树
- 1 →(2,3)，2 →(4,5)
- 输出
- 3 （路径 4→2→1→3）
先想最直接的笨办法
最直接的想法：枚举每个节点当「拐点」，再分别 DFS 求它左右子树深度、相加取最大。可每个节点都要重新往下扫一遍，深度被反复重算，整体 O(n²)。（动画第 3 步）
最优解：一步一步想明白
- 3最直接的想法：枚举每个节点当「拐点」，再分别 DFS 求它左右子树深度、相加取最大。可每个节点都要重新往下扫一遍，深度被反复重算，整体 O(n²)。
- 4转折点在这：求深度本来就要先拿到左右子树深度——那为什么不在拿到的那一刻顺手算「穿过我的路 = L+R」？一次后序遍历，每个节点深度只算一次：返回给父亲的是深度
1+max(L,R)，同时用全局变量 diam 记下所有L+R的最大值。O(n) 搞定。 - 5diam = 0后序遍历：先一路递归到最底，再从叶子往上逐个结算。先沿根 1 → 2 往左下扎。全局 diam 初始 0。
- 6depth(4)=1, diam=0到叶子 4：它没有孩子，L=R=0，
depth(4)=1+max(0,0)=1。穿过它的路 = 0+0 = 0，diam 不变。把深度 1 返回给父亲 2。 - 7depth(5)=1, diam=0回到 2 再走右孩子 5：同样是叶子，
depth(5)=1，穿过它 0，diam 还是 0。返回 1 给 2。（4 已结算，标灰） - 8L=1, R=1两个孩子都回来了：节点 2 拿到左深 L=1、右深 R=1。现在它手里有了「左右两条最深的腿」，可以结算了。
- 9穿过2 = 1+1 = 2 → diam=2在 2 这里结算两件事：穿过 2 的路 = L+R = 2（就是 4→2→5），更新 diam=2；但返回给父亲 1 的是深度 = 1+max(1,1)=2（只能挑一条腿往上接）。这两个值不一样，是全题最容易混的地方。
- 10depth(3)=1, diam=2回到根 1，再走右孩子 3：叶子，
depth(3)=1，穿过它 0，diam 维持 2。返回 1 给根。 - 11L=2, R=1根 1 拿到左深 L=2（来自 2 那一支）、右深 R=1（来自 3）。最后在根这里结算。
- 12穿过1 = 2+1 = 3 → diam=3穿过根的路 = L+R = 2+1 = 3，正是 4→2→1→3。更新 diam=3。整棵树后序走完，diam 不再变大，3 就是答案。
- 15这是一类树形题的通用套路：递归返回一个“能拼给父节点”的量（比如深度），同时用全局变量记录一个“在当前节点结算”的答案（比如穿过它的路径）。像最大路径和(124)、最长同值路径都是这个套路。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：返回 L+R 给父亲
✓ 对：返回 1+max(L,R)
给父亲的是深度(只能选一条边往上)，不是横跨路径
✗ 错：直径按节点数算
✓ 对：直径是边数 = L+R
深度按节点、直径按边，差一要分清
完整代码（Python / C++ / Java）
Python
class Solution:
def diameterOfBinaryTree(self, root):
ans = 0
def depth(node):
nonlocal ans
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
ans = max(ans, left + right)
return max(left, right) + 1
depth(root)
return ansC++
class Solution {
int ans = 0;
int depth(TreeNode* node) {
if (!node) return 0;
int left = depth(node->left);
int right = depth(node->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) { depth(root); return ans; }
};Java
class Solution {
int ans = 0;
int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) { depth(root); return ans; }
}套路模板 · 返回值 + 全局答案（背下来）
self.ans = 初值
def dfs(node):
if not node: return 0
L, R = dfs(node.left), dfs(node.right)
self.ans = max(self.ans, 用 L,R 在此结算) # 经过当前点的答案
return 能向上拼接的量(L, R, node) # 给父亲用class Solution {
int ans = 0;
int depth(TreeNode* node) {
if (!node) return 0;
int left = depth(node->left);
int right = depth(node->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) { depth(root); return ans; }
};class Solution {
int ans = 0;
int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
ans = Math.max(ans, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) { depth(root); return ans; }
}复杂度
时间复杂度
O(n)
一次后序遍历
空间复杂度
O(h)
递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树的直径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
直径为什么不一定经过根？+
最长路径可能在某棵子树内部「拐弯」。所以要在每个节点都用 左深+右深 结算一次、取全局最大，不能只看根。
直径是边数还是节点数？+
LeetCode 定义为边数 = 路径上节点数 − 1。代码里 ans=max(ans, 左深+右深)，左右深各自就是边数，直接相加。
和「二叉树的最大路径和 LC124」什么关系？+
同一套「返回值+全局答案」框架：返回给父亲只能一条边、全局答案在每点结算两边。直径结算深度，路径和结算节点值。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。