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右子树高度是11-3所以经过节点1的候选直径是 3 1 4。节点2的左子树高度是22-4-6右子树高度是22-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 两种解法的本质差异对比维度双递归解法单次递归解法计算次数每个节点高度被反复计算每个节点只访问一次时间复杂度O(n^2)O(n)代码量多一个辅助函数一个递归函数搞定理解难度直观但容易超时需要理解边算边更新的思想4. 高度定义的口径陷阱节点数还是边数深度、高度题目之间怎么换算这个坑我刷题初期踩过好几次必须单独拎出来说。LeetCode上的二叉树题目不同的题对深度/高度的口径并不完全一致。有的题按节点数算比如二叉树的最大深度104题返回的是从根节点到最远叶子节点的节点数空树返回0单节点树深度是1。有的题按边数算比如本题543路径长度按边数计。这导致了什么后果呢如果你从104题那边带着惯性来写543递归返回的是节点数高度单节点返回1那么你在每个节点算候选直径时用的是leftHeight rightHeight。这个值是节点数加出来的它比真正的边数直径多1还是少1我们来仔细算一下。假设一棵树只有根节点没有孩子。104题的深度是1543的直径是0。如果你用节点数高度来算leftHeight rightHeight 0 0 0刚好等于直径没问题。假设一棵树是 根-左孩子深度按节点算是2直径按边算是1。你算leftHeight 1rightHeight 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返回1diameter仍然是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看着对树是根-左孩子时left1right0返回1看着也对但一旦直径藏在子树内部就错了。举一个例子1 / 2 / \ 4 5这棵树里直径是24-2-5经过根节点1的路径最长只有14-2-1。上面那种错误写法会得到 left 2, right 0返回2。这里碰巧对了因为高度值里包含了左子树内部的直径候选。但如果左右子树都有深度而最长的路径却在某一侧内部就会算错。比如1 / \ 2 3 / \ 4 5 / 6这棵树直径是36-4-2-5但 left 3从1到6right 11到3left right 4错误因为路径 6-4-2-5 根本不经过节点1而经过节点1的最长路径是 6-4-2-1-3边数是4……等等这样看 leftright4 又对了我再构造一个更清晰的错误例子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为什么要这样算非常困惑直到手模了一棵四层高的树才彻底想通。这个手模的过程也是我建议所有读者一定要自己走一遍的步骤。