二叉树直径求解全解析：递归框架、高度口径与常见误区

1. 从"最大深度"到"直径"：这道题到底在问什么

先看题目本身。LeetCode 543题"二叉树的直径"（Diameter of Binary Tree），给一棵二叉树，要求返回它的直径长度。所谓直径，定义是：树中任意两个节点之间路径上边的数目最大值。

这个定义第一眼会让人犯迷糊，很多新手会误以为直径必须经过根节点。实际上不是，直径可以完全落在左子树或者右子树内部，也可以横跨左右子树。题目里的例子很典型：一棵只有左子树很深的树，直径可能根本不经过根。

那这个"边的数目"和"节点的数目"之间是什么关系？这是个高频混淆点。二叉树的深度（或者叫高度），通常定义为从根节点到最远叶子节点的节点数，或者边数，取决于具体实现。而LeetCode 543里明确说的是"边的数目"（number of edges along the path）。也就是说，如果一条路径经过了3个节点，那么这条路径的边长就是2。

这里我直接把这道题和经典的"二叉树最大深度"放在一起对比，因为它们本质上是同一个递归框架，只是统计的东西不一样：

换句话说，直径问题的核心，是在计算每个节点左右子树高度的同时，顺手把"左高 + 右高"作为一个候选答案，去更新全局最大值。这就把一道看似陌生的题，拉回到了我们熟悉的递归求深度框架里。

2. 为什么"左高 + 右高"就是直径候选值：从路径必然经过最高公共祖先这个事实说起

我在刷题群里见过很多人直接背代码，背会了但一问为什么就卡壳。这里我用一个比较直观的方式来拆解。

任意两个节点之间，一定存在一条唯一的简单路径。这条路径上，必然有一个节点是"分岔点"——也就是路径上最高的那个公共祖先节点。比如节点A在左子树深处，节点B在右子树深处，那么它们路径的最高点就是当前的根节点。又比如节点A和节点B都在左子树里，那么它们路径的最高点就是左子树里的某个节点，而不是整棵树的根。

所以，任何一条路径，都可以被看成是"从某个节点出发，往左子树方向走到某个节点的距离"加上"从该节点出发，往右子树方向走到某个节点的距离"。而往一个方向能走得最远的距离，正好就是那个方向子树的高度（以边数计）。

于是就有这个关键结论：

对于任意一个节点，经过它并且以它作为路径最高点的最长路径长度 = 左子树高度 + 右子树高度。

这里的左右子树高度，都得是以边数来计。如果用递归求节点数的那种高度定义，最后记得把统计结果调整成边数口径。

所以整棵树的直径，就是遍历所有节点，对每个节点计算这个"左高+右高"，取最大值。

为了更直观理解，我构造一个例子：

1 / \ 2 3 / \ 4 5 / \ 6 7

在这棵树里：

• 节点1的左子树高度是3（路径 1->2->4->6，边数是3），右子树高度是1（1->3），所以经过节点1的候选直径是 3 + 1 = 4。
• 节点2的左子树高度是2（2->4->6），右子树高度是2（2->5->7），所以经过节点2的候选直径是 2 + 2 = 4。
• 节点4、5、6、7的左右子树高度都是0，候选值都是0。

最终直径是4。注意，这里两个候选值相等，但代表的路径完全不同：节点1贡献的路径是 6->4->2->1->3，节点2贡献的路径是 6->4->2->5->7。

这个例子也解释了为什么不能简单用"左深度+右深度"只算一次根节点——因为最深的两片叶子可能位于同一侧子树内部。

3. 两种经典解法：自顶向下DFS的双递归，与自底向上的单次遍历

3.1 直观但啰嗦的解法：双递归，每一层都重新求深度

很多人第一反应是：我写一个函数求某个节点的最大深度，然后再写一个函数遍历所有节点，对每个节点算"左深度+右深度"，更新答案。

用C++写大概长这样：

// 求以 root 为根的子树最大深度（以边数计） int depth(TreeNode* root) { if (root == nullptr) return 0; return 1 + max(depth(root->left), depth(root->right)); } // 遍历每个节点，计算左深+右深，更新答案 void dfs(TreeNode* root, int& ans) { if (root == nullptr) return; ans = max(ans, depth(root->left) + depth(root->right)); dfs(root->left, ans); dfs(root->right, ans); } int diameterOfBinaryTree(TreeNode* root) { if (root == nullptr) return 0; int ans = 0; dfs(root, ans); return ans; }

这个解法能过，但时间复杂度是O(n^2)的。因为在每个节点上，depth函数都要递归访问它子树里的所有节点。如果树严重不平衡（比如退化成一个链表），那么总的时间开销就是 1 + 2 + 3 + ... + n，也就是 O(n^2)。

力扣数据量小的时候能AC，但这显然不是最优做法。真正的标准解法是一遍递归同时做两件事。

3.2 标准解法：单次递归，深度和直径一起算

核心思路：在递归计算每个节点高度的过程中，同时计算"左高度 + 右高度"，更新全局直径。

C++解法：

class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int diameter = 0; depth(root, diameter); return diameter; } private: // 返回以 node 为根的子树高度（边数），并更新 diameter int depth(TreeNode* node, int& diameter) { if (node == nullptr) return 0; int leftHeight = depth(node->left, diameter); int rightHeight = depth(node->right, diameter); // 经过当前节点且以当前节点为最高点的最长路径长度 diameter = max(diameter, leftHeight + rightHeight); // 返回当前子树的高度给父节点用 return 1 + max(leftHeight, rightHeight); } };

时间复杂度和空间复杂度都是O(n)。空间复杂度主要是递归栈的深度，最坏情况下链表树会压到O(n)层。

这里有一个细节要强调，也是我在留言区看人问得最多的：

为什么 diameter 的更新用的是 leftHeight + rightHeight，而不是 leftHeight + rightHeight + 1，也不是 leftHeight + rightHeight + 2？

原因是：leftHeight表示从当前节点到左子树最远叶子节点的边数，rightHeight同理。把这两条边数加起来，正好等于路径经过的总边数。比如当前节点左子树最深的那条链是 当前节点 -> A -> B，边数是2；右子树最深是 当前节点 -> C，边数是1；那么经过当前节点的最长路径就是 B -> A -> 当前节点 -> C，边数是 2 + 1 = 3。所以直接用两个高度相加即可。

Python版本会更简洁：

class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: diameter = 0 def depth(node: Optional[TreeNode]) -> int: nonlocal diameter if not node: return 0 left = depth(node.left) right = depth(node.right) diameter = max(diameter, left + right) return 1 + max(left, right) depth(root) return diameter

注意Python里用nonlocal声明 diameter，否则在内层函数里赋值会报错。这是新手比较容易卡住的地方。

3.3 两种解法的本质差异

4. 高度定义的口径陷阱：节点数还是边数？深度、高度题目之间怎么换算

这个坑我刷题初期踩过好几次，必须单独拎出来说。

LeetCode上的二叉树题目，不同的题对"深度/高度"的口径并不完全一致。有的题按节点数算，比如"二叉树的最大深度"（104题），返回的是从根节点到最远叶子节点的节点数，空树返回0，单节点树深度是1。有的题按边数算，比如本题543，路径长度按边数计。

这导致了什么后果呢？

如果你从104题那边带着惯性来写543，递归返回的是"节点数高度"（单节点返回1），那么你在每个节点算候选直径时，用的是leftHeight + rightHeight。这个值是节点数加出来的，它比真正的边数直径多1还是少1？我们来仔细算一下。

假设一棵树只有根节点，没有孩子。104题的深度是1，543的直径是0。如果你用"节点数高度"来算，leftHeight + rightHeight = 0 + 0 = 0，刚好等于直径，没问题。

假设一棵树是 根->左孩子，深度按节点算是2，直径按边算是1。你算leftHeight = 1，rightHeight = 0，加起来是1，刚好等于直径。

再看两个孩子的例子：根有左孩子和右孩子，每个孩子都没有孙子。节点数深度是2，边数直径是 1 + 1 = 2。leftHeight + rightHeight = 1 + 1 = 2，还是对的。

看起来好像无论按哪种口径，leftHeight + rightHeight直接相加，得到的都是正确答案？这其实是很多题解没有解释清楚的一个巧合。

仔细想一下：如果递归返回的是节点数高度，那么对于某个节点而言，它子树里最深的叶子到它之间的距离（以节点数计）就是它的高度值。比如节点A的左孩子存在但右孩子为空，那么节点A的左边到叶子距离是1（按节点数，A到左孩子算1个边，但返回的高度是2）。等等，这里有点绕，我换一种更清楚的方式。

实际上，在"高度按节点数算"的写法里，空节点返回0，叶子节点返回1。那么叶子节点到父节点的"高度差"是0还是1？

假设叶子节点L，它的高度 height(L) = 1。它的父节点P的高度 = 1 + max(height(L), ...) = 2。那么从P的角度看，到L这条链上的边数应该是1，但用 height(L) 的值来代表距离就是1，恰好对上了边数距离。

再用空节点来说：如果P的左孩子是空，height(null) = 0，那P的左子树方向能走的边数就是0，也就是P不能再往左走。

所以你会发现一个有趣的事实：

在"节点数高度"的语义下，height(child) 这个返回值，恰好就是从父节点出发到该孩子子树最深叶子的边数距离。

因为 height(叶子) = 1，而从父节点到叶子确实只有1条边。height(有孙子的节点) = 2，从父亲节点到最深孙子的边数也是2。所以，leftHeight + rightHeight无论按哪种口径，直接相加都正好等于边数直径。

这也是为什么很多题解里压根不提口径问题，也没写错。但我还是建议大家脑子里要装着这个口径概念，因为如果不理解这一点，当你自己改代码或者在面试中被面试官追问时，很容易被"那为什么不是 leftHeight + rightHeight + 1"这种问题问住。

面试里的加分回答是这样的：

"我这里的递归函数返回的是以当前节点为根的子树高度，按边数计。对于当前节点来说，左子树的边距离是 leftHeight，右子树的边距离是 rightHeight，两点路径以当前节点为最高点时的长度正好是两者之和。然后我每个节点都尝试用这个值去更新全局直径。"

5. 实测提交中的边界条件与常见误区

5.1 空树和单节点树

空树返回0，这个没什么争议。但单节点树呢？根节点没有任何边，所以直径是0。

如果你写出了这样的代码：

int diameterOfBinaryTree(TreeNode* root) { if (root == nullptr) return 0; int diameter = 0; depth(root, diameter); return diameter; }

单节点时，depth返回1，diameter仍然是0，输出0，正确。

但有一种常见错误写法是：

int diameterOfBinaryTree(TreeNode* root) { if (root == nullptr) return 0; int left = depth(root->left); int right = depth(root->right); return left + right; // 错！只考虑了经过根节点的路径 }

这写法在单节点时返回0，看着对；树是"根-左孩子"时，left=1，right=0，返回1，看着也对；但一旦直径藏在子树内部就错了。

举一个例子：

1 / 2 / \ 4 5

这棵树里直径是2（4->2->5），经过根节点1的路径最长只有1（4->2->1）。上面那种错误写法会得到 left = 2, right = 0，返回2。这里碰巧对了，因为高度值里包含了左子树内部的直径候选。但如果左右子树都有深度，而最长的路径却在某一侧内部，就会算错。比如：

1 / \ 2 3 / \ 4 5 / 6

这棵树直径是3（6->4->2->5），但 left = 3（从1到6），right = 1（1到3），left + right = 4，错误！因为路径 6->4->2->5 根本不经过节点1，而经过节点1的最长路径是 6->4->2->1->3，边数是4……等等，这样看 left+right=4 又对了？

我再构造一个更清晰的错误例子：

1 / 2 / \ 4 5 / \ 6 7 / 8

这个树里，真正的最长路径是 8->6->4->2->5->7，边数是5。而经过根节点1的最长路径是 8->6->4->2->1，边数是4。错误写法会返回 4，而不是正确答案 5。

所以记住：直径不一定要经过根节点，所以不能只算根节点的左右高度之和。

5.2 递归深度与栈溢出

对于极度不平衡的二叉树（例如每个节点只有左孩子，退化成一个链表），递归深度会达到n。在LeetCode的测试数据里，n最大大概是10^4量级，C++默认栈基本能撑住，Java、Python也没多大问题。但如果n到10^5或者10^6，递归就危险了。

如果真的遇到超大链表树，可以考虑迭代版本。不过说实话，刷题阶段遇到这种数据规模的概率很低，面试时也极少让你写非递归版本。知道这个风险点即可。

迭代思路是：后序遍历二叉树，用哈希表或数组记录每个节点的左右子树高度，然后同样在每个节点处累加更新直径。但代码会明显变长，可读性也下降。我个人的建议是，笔试或面试优先写递归版本，等真遇到栈溢出再说。

5.3 直径为什么是边长而不是节点数

题目里明确写了"number of edges along the path"，有些题（比如"树的直径"变体）可能定义成节点数。如果刷题时发现答案差1，去翻一下原题描述里的口径。

这里有一个通用换算技巧：如果按节点数算路径长度，那么一条包含k个节点的路径，边长是k-1。在543这道题的代码里，leftHeight + rightHeight算出来的是边数。如果你想得到节点数版本的直径，只需要最后加1即可，但要注意空树的特判。

6. 变体与进阶：从直径到"所有树上路径问题"的统一思考框架

543这道题做完之后，千万别急着划走。它其实是一大类树上路径问题的入口。理解了"在节点处用左右子树信息合并更新全局答案"这个套路，很多hard题都能拆解。

常见的变体有：

• 124. 二叉树中的最大路径和：每个节点有值，路径和定义为路径上所有节点值之和。做法一样是后序遍历，每个节点处尝试用leftGain + node->val + rightGain更新全局答案，然后向上返回单侧最大贡献值。区别在于，如果某个子树的贡献是负数，就舍弃它，当作0处理。

• 687. 最长同值路径：找最长的路径，使得路径上所有节点值相同。做法也是后序遍历，但只有在子节点值和当前节点值相等时，才把那个方向的高度计入候选左右路径。

• 树形DP类问题：比如"监控二叉树"（968题）这种，状态转移也是在每个节点处组合左右子树的多种状态。

• 所有节点到某个目标节点的距离和：比如"二叉树中所有距离为K的节点"（863题），用图论BFS或两次DFS处理。

所以543的价值，不只是背一道简单题，而是建立起一个思维模型：

凡是"树上任意两点路径相关的极值问题"，优先想后序遍历，在每个节点用左右子树的信息合并一次，向上只返回单一方向的"贡献值"。

回到543这道题本身，我把最终可提交的代码再贴一遍。刷题时直接参考这一版就够：

class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int diameter = 0; height(root, diameter); return diameter; } private: int height(TreeNode* node, int& diameter) { if (!node) return 0; int left = height(node->left, diameter); int right = height(node->right, diameter); diameter = max(diameter, left + right); return 1 + max(left, right); } };

代码短到只有9行，但这里面包含的"全局变量更新 + 单侧返回值"思想，是后续几十道树上DP题的基石。建议你把这9行代码背熟，再亲手在纸上画几棵不同形状的树，逐步模拟递归栈过程，比直接看一百遍题解都管用。

我在实际刷题中还有一个习惯：每做完一道树题，会顺手把这道题的递归过程和"最大深度"那道题的递归过程并排写下来，对比它们每一步返回值的含义。第一次做543时，我也对leftHeight + rightHeight为什么要这样算非常困惑，直到手模了一棵四层高的树才彻底想通。这个手模的过程，也是我建议所有读者一定要自己走一遍的步骤。