这是某刷题列表里的第39道经典题名字叫“二叉树的直径”。别看问题描述只有一句话它却是很多人栽在二叉树递归上的第一个坎求一棵二叉树中任意两个节点之间最长路径的长度。我第一次做的时候天真地以为要找“树最宽的位置”结果样例一跑就完全翻了车。这道题真正的价值不在于背一份答案而在于彻底搞明白三件事路径为什么一定能在某个节点处分叉、递归函数到底该返回什么、全局最大值该怎么维护。这篇文章就按我实际思考的过程来写从题目拆解到代码实现再到测试用例设计把我踩过的坑和总结出来的关键点全都摊开讲一遍。1. 题目拆解先弄清“直径”到底在求什么1.1 从一棵树的形状说起先明确定义。二叉树的直径指的是树中任意两个节点之间最长路径的“边数”。注意两个关键词第一是“任意两个节点”说明起点和终点不一定是叶子节点可以是树里任何位置第二是“边数”这是最经典的口径但不少变体题会要求统计“节点数”这两种口径在同一棵树上答案会差1做题前务必看清题目描述。举个例子帮助理解。假设一棵树只有根节点和一条向左延伸、深度为3的链那么最远的两个点就是根和这条链最深处的叶子路径边数是3所以直径就是3。但如果树左右两边都有深度不小的子树最远的那两个点大概率是“左子树某个叶子”和“右子树某个叶子”路径会经过根节点整条路径的长度就是左子树深度加右子树深度。这里最需要区分开的概念是“直径”和“高度”。树的高度是根节点到最远叶子节点的距离方向性很强一定以根为起点而直径是整棵树中任意两点间的最大距离它完全可以不经过根。比如根节点只有一个很深的左子树而这个左子树内部又有一棵形状复杂的子树最远的两个点很可能都藏在左子树里这时候直径跟根节点一点关系都没有。我刚接触这道题时就是没想通这一点导致写出来的代码只在处理“经过根”的情况一遇到复杂树就错。1.2 直径与深度的关系既然最长路径可以藏在任意一棵子树内部一个朴素但又非常正确的思路就是枚举这条路径可能经过的“最高点”。对于任何一条路径把它从中间拎起来一定存在一个节点它位于这条路径的最上方也就是这条路径上所有节点的公共祖先中深度最浅的那一个。路径在这个节点处被分成两段一段向左子树方向延伸另一段向右子树方向延伸当然也允许只有其中一段。于是整棵树的直径就可以转化为一个非常局部的计算对树中每个节点算出它左子树的最大深度加上右子树的最大深度然后取所有这些值里的最大值。这里的“左子树最大深度”是指从当前节点出发、沿着左孩子一路向下最多能走多少条边右子树同理如果某一边为空那对应深度就是0。这个转化是整个题目的核心洞察它把“找出任意两节点间的全局最长路径”这个看着无从下手的问题拆成了每个节点上只和左右子树深度有关的局部算式。而“每个节点的左右子树深度”又恰好能通过一次深度优先遍历自底向上算出来这就自然引出了后面的递归解法。我每次讲这道题都会强调这个“拎起来”的比喻你随便找一条路径找到它最顶端的那个分叉点剩下的问题就是计算这个分叉点左下方和右下方各能延伸多远。2. 算法设计为什么后序遍历几乎是这个题的唯一正解2.1 自底向上的计算顺序要计算某个节点的左右子树深度就必须先完整处理完它的左子树和右子树拿到左右子树各自返回的深度值之后才能做加法和比较。这种“先处理孩子、再处理自己”的顺序正是二叉树的后序遍历。你可以对比一下前序遍历如果先访问某个节点再访问它的子树那在这个节点上你根本不知道子树的信息自然也就没法计算直径。所以这道题天然依赖后序遍历这不是做题习惯的问题而是信息依赖关系决定的——父节点的计算建立在子节点的结果之上你必须先把下面摸清楚才能向上汇报。很多初学者会问“能不能在一次递归里同时把深度和直径都算出来”。完全可以而且这正是最优做法。我们只需要让递归函数做两件事第一把左右子树深度相加用这个和去更新全局直径最大值第二向父节点返回当前子树的深度也就是左右子树深度中的较大者再加1。这样每一层递归同时完成了局部答案的更新和向上汇报两个职责。我形容这种写法是“一鱼两吃”一次遍历不浪费任何信息。2.2 递归函数返回什么这里是最容易写错的地方也是面试官最爱追问的点。递归函数返回的一定是“以当前节点为根的子树的深度”而不是直径本身。直径是通过一个全局变量或者闭包外的容器一点点累加出来的。为什么不能把直径也放进返回值里因为直径的定义是两个节点之间的距离它是一个全局性质不依赖任何一个固定的根而深度是局部的、有明确根节点的量。如果把两个信息都塞进返回值递归函数的签名会变得很别扭而且上层节点其实只需要子树的深度来参与计算它并不关心子树内部的直径是多少。一个清晰的递归函数应当只返回一个语义明确的值这是写递归的基本功。我在代码评审时看到最头疼的代码就是那种返回值为元组、还得靠下标取数据的写法能跑通但可读性极差。2.3 时间与空间复杂度每个节点在递归中恰好被访问一次递归内部的加法、比较都是常数时间所以时间复杂度是O(n)n是节点总数。空间复杂度则取决于递归调用栈的深度也就是树的高度最坏情况下一棵退化成链的树高度为n空间复杂度是O(n)平均情况下平衡二叉树的高度是O(log n)空间复杂度也就是O(log n)。关于空间复杂度我多说一句。很多同学觉得递归的空间复杂度不好判断其实你只要问自己一个问题函数调用栈最深能压多少层答案就是树高。所以“平均O(log n)、最坏O(n)”这个结论要牢牢记住在面试里几乎属于必背的输出。如果你面对的是一棵可能出现极端形状的树写代码前就要想好递归深度会不会爆栈这个我在第4节会详细展开。3. 代码实现从基础版到细节打磨3.1 Python基础实现直接上代码这是我刷题时一直使用的版本class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def diameter_of_binary_tree(self, root): self.diameter 0 def postorder(node): if node is None: return 0 left_depth postorder(node.left) right_depth postorder(node.right) self.diameter max(self.diameter, left_depth right_depth) return max(left_depth, right_depth) 1 postorder(root) return self.diameter我把全局直径记录放在Solution实例属性self.diameter上作用是充当整个递归过程中的“公共便签”。有人会问为什么不直接用普通局部变量因为在Python的嵌套函数里如果要在内层函数中修改外层函数里的局部变量必须用nonlocal关键字声明否则Python会把它当成一个新的局部变量结果就是外层那个变量始终没有被更新题目直接算错。用self.xxx恰好绕开了这个声明问题既简洁又稳定。如果你更喜欢函数式一点也可以显式使用nonlocaldef diameter_of_binary_tree(root): diameter 0 def postorder(node): nonlocal diameter if node is None: return 0 left_depth postorder(node.left) right_depth postorder(node.right) diameter max(diameter, left_depth right_depth) return max(left_depth, right_depth) 1 postorder(root) return diameter两种写法效果完全一样差别只是编码风格。我两个版本都在本地跑过同样的测试用例性能上没有区别。选哪种取决于团队约定和个人口味但理解nonlocal和实例属性的区别是必要的面试时如果被问到“这段代码里diameter为什么能更新”你得能说清楚背后的变量作用域规则。3.2 变体题目统计节点数有些变形题会把问题改成“求最长路径上的节点数”。这时候最省事的做法就是把最终答案加1因为一条包含x条边的路径上面的节点数是x1。但也有另一种实现方式在更新答案时直接写成left_depth right_depth 1而递归返回值仍然保持max(left_depth, right_depth) 1。无论哪种方式最终结果都是一致的。我建议你做题之前先看清楚题目要求的是边数还是节点数再看题目给的示例验证一下自己的理解。按边数口径返回的话单节点树的直径是0按节点数口径返回单节点树是1。这两个数字是刚入门最容易搞混的细节很多提交失败的案例都是因为口径没对齐而不是算法本身有问题。所以拿到题第一件事不是写代码而是先确认输出单位。3.3 空树与单节点的边界处理如果题目允许传入空的根节点直径应该是0。上面的代码天然处理了这种情况postorder(None)直接返回0直径保持初始值0。别小看这一行判空代码里所有递归的终止条件都靠它删掉必崩。不少在线评测平台给的输入用例里偶尔会有root None的情况如果你在本地写测试时不处理空指针在核心代码模式下可能不会崩但一旦把逻辑搬到需要完整处理输入输出的工程环境里就会暴露问题。我的习惯是任何树相关的递归函数第一句永远是判空这已经成为肌肉记忆。宁可多写一行也不要让空指针异常在线上炸开花。另外单节点树的处理也能顺带检验你对口径的理解。用上面的代码root只有一个节点时postorder(root)会走到左右子树为空的递归left_depth和right_depth都是0更新时diameter保持0返回1给上层最后函数返回0。这是正确的一条边都没有直径当然为0。4. 踩坑记录与调试实录4.1 最常见的三类错误我见过不少人在这个题上反复提交不过虽然报错信息五花八门但总结下来核心错误其实就三类。第一类是“只比较了根节点的左深度加右深度”。很多第一版代码写成下面这样# 错误示意depth 函数单独计算子树深度 def diameter_of_binary_tree(root): if root is None: return 0 return depth(root.left) depth(root.right)这个写法完全忽略了直径可能在某一棵子树内部。比如根的左子树里有一条很长的路径但根的右子树为空上面这种写法算出来的直径直接是0或者很小显然错误。这就是前面反复强调的那个点直径不必经过根节点。第二类是递归函数错误地返回了直径。也就是说在postorder里最后一行写成return self.diameter而不是return max(left_depth, right_depth) 1。这样父节点拿到的不是子树的深度而是一个全局累积值加1之后彻底失去意义最终结果往往偏大且很不稳定。递归函数的返回值必须是“本层子树深度”这一点要刻在脑子里。第三类是忘记使用max做全局更新。有些人图省事直接写self.diameter left_depth right_depth这样会丢掉之前已经找到的更优答案。直径要求的是所有节点里计算结果的最大值不等于最后一个被访问的节点就是最优的。后序遍历的顺序和答案的大小没有关系必须用max逐级比较。4.2 测试用例设计清单我每次本地调试固定跑这么几类用例拿出来分享大家可以直接参考用例场景树结构描述期望直径边数口径空树根节点为None0单节点只有根节点0一条链1-2-3-4依次相连3满二叉树高度为3的完全二叉树4单边深树左子树很深右子树为空等于左子树深度举一个具体例子构造一个根节点它的左子树高2右子树高3那么直径期望是5。再比如一条从根开始一直往右延伸、深度为10的链正确直径就是10。这些用例每跑一遍代码对不对基本一目了然。我实际调试时还会特意构造一个“直径不经过根节点”的场景根只有左孩子左孩子下面挂了两个子节点这两个子节点又各自延伸出不短的链。这种情况下最远路径完全在左子树内部直径和根节点无关。这个用例能有效检验你是否真的用了全局更新而不是只处理根节点。如果你写完代码后发现这个用例跑不对十有八九就是踩了第一类错误。4.3 递归深度的现实问题用Python刷这道题在常规评测数据下没什么问题。但如果树的节点特别多且退化成一条链递归深度可能超过Python默认的递归上限通常约1000层。经典题目故意设计的数据规模一般不会让你遇到这个坎但我在本地做压力测试时确实崩过。解决办法有两个。第一个是写迭代版的后序遍历用显式栈模拟系统的递归调用。第二个是直接调大递归限制比如用sys.setrecursionlimit。但调大限制在真实线上环境不推荐因为它只是暂时延后问题并没有消除深栈可能带来的崩溃风险。我给自己定过一个标准如果树的高度可能超过几百优先考虑迭代写法。工程里的树一般都不算浅尤其是从业务数据构建出来的树形状完全不可控。宁可多写几行代码也换一个不依赖系统调用栈的方案。5. 延伸从二叉树的直径到更广的场景5.1 N叉树的直径一法通则百法通。如果题目从二叉树变成N叉树核心思路完全一致对于每个节点找出所有孩子返回的深度值里最大的两个相加去更新全局答案然后返回这些深度值中的最大值再加1。关键的差别在于N叉树一个节点可能有多个孩子你需要维护“最大”和“次大”两个深度值。我见过有人在这里用排序其实完全没必要用一个两元素的扫描就能在O(1)额外空间内完成时间复杂度依然是O(n)。这个小优化在复杂度分析上没什么差别但写起来更干净也不会引入不必要的排序开销。5.2 带权边的直径再往外走一步如果树的每条边带权重直径的定义就变成“任意两节点间路径权重之和的最大值”。做法还是同一套后序遍历只是在返回时不再简单加1而是要带上边的权重return max(left_weight, right_weight) edge_weight。这种变体在树形网络监控、分布式系统计算节点间最大时延的场景里很常见。你可能会在一道看似普通的算法题里遇到一个披着网络监测外衣的“带权直径”本质上还是我们这套后序遍历的骨架。熟练了基础版这种变形也就是换几个加数的事。5.3 和“树的最大深度”的关系最后想聊一个容易被忽视的点。二叉树的直径这道题本质上是“树的最大深度”的一次升级。最大深度只需要子树深度中的最大值再加1直径则是把两个子树的深度加起来再和全局答案取最大。这两道题经常在刷题列表里挨着出现我强烈建议把它们放在一起刷对比着看递归结构。最大深度让你理解“返回什么”直径让你理解“全局答案怎么更新”两个题结合起来一次就能把后序遍历最常见的两种应用吃透。很多人在树相关的题目上反复卡壳就是因为始终停留在背代码阶段没有把这两层逻辑拆开。6. 最后说点我自己的体会回到开头那句话这道题到底难不难它其实不难但确实卡住了很多初学递归的人因为陷阱藏在“返回什么”和“更新什么”这两个细节里。我个人刷了这些年树相关的题最大的一个感悟是凡是这种在遍历过程中需要“带一个全局答案到处跑”的题目都可以先画一棵小树把递归函数每一步的返回值手写出来再对着代码逐行核对。这个方法虽然慢但真的能帮你看透递归的每一层在做什么。再分享一个小技巧面对任何树相关的题动笔写代码前先问自己三个问题——递归函数要返回什么局部信息要不要更新一个全局答案终止条件是什么把这三个答案写在草稿纸上代码基本就成型了。二叉树的直径正是练习这个思维框架最好的素材之一。这个框架以后还能直接迁移到树的最近公共祖先、二叉树路径和等问题上外壳不同内核都是同一套遍历思想。