企业官网建设流程全解析

二叉树的直径，刷题路上绕不开的一道经典递归题。很多人第一次看到“直径”两个字，下意识觉得是在求树里最远的两个节点之间的距离，方向确实没错，但真正动手写代码时，却常常卡在“直径不一定经过根节点”这个点上。热门题单里的编号35，说的就是这道题，今天这篇就把它彻底拆开，从定义、递推、代码到边界用例一次讲清楚。适合刚入门二叉树、准备面试、想把递归框架用熟练的同学，也能帮已经会做的人补齐理解深度。

1. 题目到底在问什么：把“直径”翻译成人话

1.1 从定义到直觉

题目原文很简洁：给定一棵二叉树，返回它的直径。这里的直径定义为“任意两个节点之间路径长度中的最大值”，而路径长度指的是两个节点之间的边的数量。

很多人第一次看到“直径”会联想到几何里的圆的直径，但在二叉树里完全没有这层意思，它只看两个节点之间有多远。两个节点之间的路径是唯一的，沿着父节点指针往上走，总能找到一个公共祖先，路径就是从节点A上溯到祖先，再下探到节点B。路径上穿过的边的条数，就是这两个节点之间的距离。

一棵树的直径，就是所有节点对之间距离的最大值。换句话说，找两个点，让它们之间的边数尽可能多。

这里有个容易忽略的点：题目没有限定“路径必须经过根节点”。恰恰相反，很多最大距离出现在某个子树的内部，和根节点一点关系都没有。下面用一个最简单的反例就能看清。

1.2 最常见的误区：直径必须过根节点？

假设有一棵只有右子树的链状树：根节点1，右孩子2，右孩子3，右孩子4。整棵树退化成一条直线，一共有4个节点，3条边。

直觉上最远的两个节点是1和4，距离是3，这条路径确实经过根节点1。但如果把根节点往旁边挪一下，变成一棵稍微深一点的树，比如根节点的左子树很深，右子树也很深，但左右深度不对称，情况就不一样了。

更典型的反例是这样的：根节点1，左孩子2，右孩子3。2下面挂一个左孩子4，4下面挂一个左孩子5；3下面挂一个右孩子6，6下面挂一个右孩子7。这棵树的左右子树都很深，最远节点显然是5和7，路径是5—4—2—1—3—6—7，经过根节点，直径是5。

但如果把根节点的左右子树深度做成“一边特别深，另一边特别浅”，真正的最远点对可能完全落在某一条链上，根本不需要经过根节点。比如一棵退化成单链的树，链的两端距离最远，但其中间路径可能穿过一些祖先节点，如果直径计算时只考虑经过当前根节点的路径，就会漏掉真正的答案。

所以在做这道题时，千万不要把代码写成“只求左子树高度加右子树高度”。这是初学者最常见的错误，也是这道题专门设置的坑。

1.3 先算深度，再求直径：树的高度是基础材料

要理解直径解法，先得把“深度”和“高度”这两个概念理顺。不同资料里叫法有点混，这里统一说明：

• 深度：从根节点到当前节点的边的数量。
• 高度：从当前节点到最远叶子节点的边的数量。

直径的候选路径，可以看作“某个节点左子树中最深的叶子”到“右子树中最深的叶子”的距离。这条路径在这个节点处拐了一个弯，而这个节点就是路径上最高（最靠近根）的那个点。

对于任意节点X，经过X且以X为“最高点”的路径，长度等于左子树高度加右子树高度。因为从左子树最深叶子走到X需要左子树高度条边，从X走到右子树最深叶子需要右子树高度条边，加起来就是整条路径的边数。

整棵树的直径，就是所有节点上这个“左高+右高”的最大值。这样就把一个求距离的问题，转换成了求每个子树高度的问题。

高度怎么求？递归非常自然：一个空节点高度为0；非空节点的高度是左右子树高度的最大值再加1。这是二叉树递归的基石，也是后面所有解法的核心递归函数。

2. 解题前的底层准备：遍历与递归框架

2.1 为什么树的问题天然适合递归

二叉树本身就是递归定义的：一棵二叉树要么为空，要么由一个根节点和两棵二叉树组成。这个定义让递归解法成为一种“顺手”的选择。

用生活里的例子理解：公司里要统计一个部门的最高工时，部门经理只需要问两个组长的最高工时，取较大值，然后加上自己的一小时。组长再去问下面的员工。每一层做的事情一模一样，只是范围变小了。递归函数就是这样一个自动化的层级汇报机制。

在二叉树上，每个节点只需要关心两件事：左子树返回什么信息，右子树返回什么信息，然后结合自己当前节点的信息，决定向上层返回什么。这种“自底向上”的信息传递，天然对应树的递归结构。

很多树相关的题目，比如最大深度、平衡二叉树、直径、路径总和，本质都是同一个递归框架在不同信息维度上的变体。把递归树的推导练熟，等于拿到一把万能钥匙。

2.2 后序遍历：自底向上汇总信息

树的遍历有前序、中序、后序三种经典顺序。直径这道题需要的是后序遍历。

后序遍历的顺序是：先遍历左子树，再遍历右子树，最后处理当前节点。为什么直径需要后序？

因为计算当前节点的“左高+右高”时，必须已经知道左子树和右子树各自的高度，而这些高度又需要先递归求解。换句话说，当前节点的答案依赖子树的结果，必须先把子树算完，再回头算当前节点。这正是后序顺序的定义。

前序遍历适合“从根开始向下传递信息”的场景，比如求根节点到所有节点的路径和。后序遍历适合“从叶子向上汇总信息”的场景，比如求子树高度、最大直径、子树和。用错了遍历顺序，代码逻辑就会别别扭扭，甚至完全失效。

2.3 全局变量与函数返回值：两种风格的取舍

递归函数需要同时完成两个任务：向上返回子树高度，同时在每个节点尝试更新直径答案。这两个任务的信息方向不同，实现上有两种常见选择。

第一种：递归函数只返回子树高度，直径用外部变量记录。每次访问到节点X时，用左右子树高度之和去更新外部变量。这种做法直观，代码清晰，面试时最容易讲明白。

第二种：递归函数返回一个结构体或pair，同时包含“本子树高度”和“本子树内部最大直径”。这样做的好处是没有全局变量，纯函数风格，适合一些面试官较真的场合，或者做单元测试时更干净。

两种写法等价，但理解第一种是基础。因为第一种把“向上返回”和“全局更新”两个责任分得很清楚，初学者不容易绕晕。

3. 完整解法：递归DFS的推演与代码实现

3.1 状态定义与递推关系

明确一个递归函数：

dfs(node)返回以node为根节点的子树的最大高度（从根到最远叶子的边数）。

递推关系：

• 如果node为空，返回0。
• 否则递归求左子树高度L = dfs(node->left)，右子树高度R = dfs(node->right)。
• 当前节点作为路径最高点时，经过它的最长路径长度为L + R。
• 用这个值更新全局答案diameter = max(diameter, L + R)。
• 向上一层返回max(L, R) + 1，表示当前子树的高度。

整个过程只需要遍历一次所有节点，时间复杂度O(n)。每个节点都做常数次操作，没有任何重复计算。

理解递推关系的关键点在于：L + R只是“途经当前节点的最长路径”，并不是当前子树最终的直径答案。子树最终的直径可能完全在左子树内部，也可能完全在右子树内部，因此全局答案必须取所有L + R的最大值。

3.2 边界条件处理

边界条件就是空节点。空节点没有高度，返回0。

如果整棵树为空，dfs(root)会被调用一次，左右子树都是空，L + R = 0，全局答案保持初始值0，返回0，结果正确。

只有一个根节点时，左右子树为空，L + R = 0，答案也是0。两个节点的树，比如根1左孩子2，根节点的左子树高度1，右子树高度0，L + R = 1，答案1，正好是1到2的边数。

边界处理最常见的坑是把空节点返回-1。有些算高度的问题会返回-1来配合某类平衡判断，但直径这道题统一返回0最简单，也符合“高度=边数”的定义。

3.3 核心代码实现

以常见的二叉树结构为例：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: int diameter = 0; int dfs(TreeNode* root) { if (root == nullptr) { return 0; } int leftHeight = dfs(root->left); int rightHeight = dfs(root->right); // 经过当前节点的最长路径 = 左子树高度 + 右子树高度 diameter = max(diameter, leftHeight + rightHeight); // 返回当前子树的高度 return max(leftHeight, rightHeight) + 1; } int diameterOfBinaryTree(TreeNode* root) { diameter = 0; dfs(root); return diameter; } };

提示：每次调用diameterOfBinaryTree时都要把全局变量重置为0。否则如果同一个Solution实例被多次调用，上一次的结果会污染下一次答案。

这里用成员变量保存直径，是为了让dfs函数只承担“返回高度”这一个职责。实际提交时，这种做法非常稳定，不容易出错。

3.4 不使用全局变量的写法

有些场景下，比如面试官要求写一个纯函数，不希望有外部状态，就可以用返回值同时携带高度和直径：

pair<int, int> dfsWithDiameter(TreeNode* root) { if (root == nullptr) { return {0, 0}; } auto left = dfsWithDiameter(root->left); auto right = dfsWithDiameter(root->right); int height = max(left.first, right.first) + 1; int diameter = max(left.second, max(right.second, left.first + right.first)); return {height, diameter}; } int diameterOfBinaryTree(TreeNode* root) { return dfsWithDiameter(root).second; }

这里的pair第一个值表示子树高度，第二个值表示子树内部的直径。每个节点返回给父节点的直径，可能是左子树直径、右子树直径、或者“左高+右高”三者中的最大值。

这种写法和全局变量版本完全等价，只是把状态封装在了递归返回值里。我在做单元测试时喜欢用这个版本，因为可以反复调用同一个函数，不用考虑重置状态。

3.5 复杂度分析

时间复杂度：O(n)，n是节点总数。因为每个节点只被访问一次，递归函数在每个节点上的操作是常数时间。

空间复杂度：O(h)，h是树的高度。递归需要调用栈空间，最坏情况下树退化成一个链，递归深度等于节点数，空间O(n)。平均情况下，树的高度远小于节点数，空间占用没问题。

要特别注意，这里的空间复杂度不是O(1)，递归栈也是成本。某些极端情况下，10万个节点的单链树会导致递归层数达到10万，可能会栈溢出。不过面试和笔试的常规用例不会这么极端，知道结论即可。

4. 从“会做”到“做对”：边界用例与高频错误

4.1 测试用例设计

做题不能只靠平台给的几个样例，自己要在本地多构造边界情况。我最常用的一组用例：

• 空树：nullptr，期望结果0。
• 单节点：只有一个根，期望0。
• 两节点：根和左孩子，期望1。
• 三节点链：1-2-3，期望2。
• 左右子树各一条深链：根左边挂一条深度4的链，右边挂一条深度3的链，期望7。
• 完全二叉树：7个节点的满二叉树，最远叶子之间的距离是4，期望4。

最后一类用例很关键：完全二叉树里，最深的两个叶子隔着根节点，距离是左子树高度2加右子树高度2，等于4。如果代码只在某个节点计算左右高度，完全二叉树能过，但链状树可能出错。所以一定要把链状树单独测一遍。

还有一类“隐藏用例”：左子树很深但右子树为空，直径其实完全在左子树内部。这种情况下，如果代码只算根节点的左高+右高，会漏掉左子树内部的更长路径。正确解法靠全局更新，天然覆盖这种情况。

4.2 高频Bug清单

我在带人做这道题时，看过不少重复踩坑的写法，整理成清单：

第一个Bug：只计算根节点的左高+右高。这是最经典的错误，虽然题目本身没有强调，但平台用例里一定有一棵“直径不经过根节点”的树来卡你。比如根节点右子树是空，左子树是一棵很深的树，真实直径可能在左子树的内部。只算根节点会得到一个小得多的错误答案。

第二个Bug：递归返回时忘了加1。有人写return max(leftHeight, rightHeight);，导致每个节点的高度都少算一层，最终答案偏小。记住“当前节点也算一层”，必须加1。

第三个Bug：更新直径的时机不对。有人把diameter = max(diameter, leftHeight + rightHeight)写在了递归调用之前，此时左右高度还没计算出来，得到的永远是0。

第四个Bug：空节点返回-1。这个习惯是从“计算二叉树平衡因子”那类题带过来的。在直径问题里，空节点返回0才能让单节点树的直径正确为0，如果返回-1，单节点树会得到-2之类的负数，还得额外打补丁。

第五个Bug：重复递归。有人在diameterOfBinaryTree里先递归一遍求左子树直径，再递归一遍求右子树直径，又递归求左右深度。这样做功能上勉强对，但时间复杂度变成O(n^2)，遇到底层链状树直接超时。记住一次后序遍历就够。

第六个Bug：路径长度理解成节点数。题目要的是边数。每次直径都是左右高度之和，这个值天然是边数，别在最后结果上再加1或减1。

4.3 迭代法可行吗？

递归是这道题最自然的解法，但总有人问“能不能用迭代做”。答案是能，思路是用栈模拟后序遍历。

迭代后序遍历需要维护每个节点对应的高度。一个简单做法是同时压栈两次，或者手动模拟递归栈帧，记录节点状态。具体步骤大致是：

1. 用栈保存节点，并标记是否已经访问过左右子树。
2. 当左右子树都处理后，计算当前节点的左高+右高，更新答案。
3. 当前节点向上返回的高度可以存在一个哈希表里，键是节点指针，值是高度。

代码会比递归版本长不少，唯一的优势是避免递归栈溢出。但在绝大多数面试场景下，递归版本足够，而且代码更短更容易解释。我一般会主动提一句“如果树很深，递归可能爆栈，可以用栈模拟后序遍历”，显示你考虑过工程化问题，但不会真的现场写迭代版。

5. 举一反三：一道题带出整个树形DP脉络

5.1 从直径到最大路径和

二叉树的直径不带权，只看边长。把它升级一下，就变成经典的“二叉树中的最大路径和”：每个节点有一个整数值，路径上所有节点值的和定义为路径和，求最大路径和。

解法和直径如出一辙，区别在于：

• 直径里空节点的高度是0，路径长度不会为负。
• 最大路径和里，节点值可能是负数，一个子树如果和是负的，就不如不选这个子树。

递归函数在更新答案时，要计算“左子树最大贡献 + 右子树最大贡献 + 当前节点值”，但向上返回时只能返回“单侧最大贡献 + 当前节点值”，并且如果这个值是负数，就返回0，等价于放弃这个分支。

直径题不需要考虑负数，所以边界判断少一点。但从直径迁移到最大路径和，逻辑框架完全一致，只要学会处理“值可能为负”的三种情况就通了。

5.2 从直径到最长同值路径

另一个变体是“最长同值路径”：路径上的所有节点值必须相同，求这样的路径最长能有多少条边。

思路依然是用后序遍历，对每个节点计算“从当前节点出发、沿着相同值向下延伸的最大长度”。但更新答案时，只有左孩子值和当前节点值相同，才把左子树贡献加进来；右孩子同理。返回给父节点的高度，也只考虑与父节点值相同的分支。

这里的关键是“相同值”这个约束让左右子树的贡献变成了条件值，而不是无条件累加。理解了直径题的“任意贡献”和同值路径题的“条件贡献”，再看很多树形DP问题就会觉得眼熟。

5.3 扩展到N叉树的直径

如果二叉树变成N叉树，每个节点可能有很多孩子，直径怎么求？

思路还是类似的：对每个节点，找孩子中最大的两个高度，它们的和就是经过当前节点的最长路径。需要维护一个“前两大高度”，而不是简单的左加右。

实现时，递归函数返回当前子树的最大高度，同时遍历所有孩子，记录最大和次大的高度，用最大+次大更新全局答案。

其实二叉树的leftHeight + rightHeight就是“孩子高度中最大和次大的和”，因为二叉树最多两个孩子，最大和次大恰好是左右子树。理解这一层后，从二叉到N叉就是自然的扩展。

5.4 本质：子树信息汇总的树形DP

回看这些变体，核心思想一致：每个节点根据子节点返回的信息，结合自身，计算出本子树的某种指标，并把子问题最关心的信息继续向上传递。

这就是最基础的树形DP。和普通DP的区别只是“阶段”变成了“树的层级”，决策顺序受树的拓扑结构约束。二叉树的直径是树形DP里最典型的入门题，因为它没有任何状态压缩、没有权值、没有条件，纯粹展示“后序汇总”这个骨架。

很多人觉得树形DP难，其实从这一题开始做通，后面遇到打家劫舍III、监控二叉树、树的最大独立集，都能找到熟悉的感觉。

6. 实战心得与避坑经验

6.1 面试中怎么讲这道题

如果面试遇到这道题，不要拿到手就闷头写代码。先在白板上画一棵比较复杂的树，比如左右子树深度不同的那种，指着它讲清楚思路：

先定义dfs返回子树高度，然后用一个全局变量记录所有节点中“左高+右高”的最大值。为什么不是只算根节点？因为直径可能完全落在子树内部，必须遍历所有节点。

讲的时候，主动写一个反例证明“只算根节点”为什么错。这个细节能让面试官对你的理解深度刮目相看。

代码写完后，主动报复杂度：时间O(n)，空间O(h)。如果面试官追问能不能优化，可以提迭代版模拟后序，或者说O(h)已经是递归的常规下限，无法做到O(1)且不改变树结构。

还有一个小话术：解释返回值“高度”和答案“直径”是两个不同维度。高度是给父节点用的中间信息，直径是全局累计答案。把这两个概念分开讲，面试官基本不会觉得你是在背题。

6.2 三个能立刻上手的验证技巧

做完代码后，我一般会做三件事来验证正确性：

第一步，手推样例。画一棵三层的树，手动计算高度和直径，再拿代码结果对比。

第二步，跑极端用例。比如空树、单节点、退化成链的树，这些用例容易暴露“返回-1”“忘加1”之类的问题。

第三步，尝试改动代码，确认理解。比如把更新答案的语句删掉，答案会变成0；把返回值改成不加1，所有高度都错。故意破坏代码再观察结果，是检验自己是否理解递归逻辑的好方法。

这三个技巧听起来简单，但能很大程度减少“代码在平台上跑过就觉得会了”的假象。真正把每一行为什么存在的理由讲清楚，才算掌握。

6.3 我自己的体会

这道题我前后刷过好几遍，每次重看都有新的理解。第一遍时我只记得“左右高度相加”，但遇到直径不经过根节点的用例就懵了。第二遍才真正明白全局更新的必要性。第三遍能主动和最大路径和、最长同值路径串起来想。

从刷题角度说，二叉树直径的价值不在于题目本身有多难，而在于它是“递归后序处理”这个母题的最佳样品。把这道题吃透，后面一大批树的题都会轻松很多。从面试角度说，这道题代码量小、思路清晰、坑点明确，是一道性价比极高的热身题。如果你正在准备面试，建议把这题放在二叉树专题的前面，先把它的递归框架练成肌肉记忆，再往后推进。