二叉树直径（LeetCode 543）递归解法：原理、调试与变体延伸

刷LeetCode热题100的时候二叉树相关的题目里543这道“二叉树的直径”看起来人畜无害结果点开评论区发现一堆人跟我当初一样代码跑起来就是报运行时错误或者一提交就在某个隐藏用例上翻车。今天就把这道题彻底拆开从题目本质到递归实现再到调试经验和变体延伸一次性说透。这道题的核心其实就一句话在一棵二叉树中找到任意两个节点之间最长路径的边数。注意路径不一定经过根节点这也是它和“求树的深度”最本质的区别。适合刚刷完二叉树遍历、想进阶递归思维的人也适合面试前突击热题100的人。搞懂它你对“递归返回什么、全局状态如何更新”的理解会上一个台阶。1. 题目到底在问什么直径不是几何学里的直径1.1 原题描述与直觉陷阱原题给的是这样一棵二叉树要你返回它的直径长度。很多人第一眼看到“直径”两个字会下意识地以为是根节点左子树深度加右子树深度也就是经过根节点的最长路径。这个直觉在部分用例下是对的但放到完整题目里就成了最大的坑。因为最长路径完全可能不经过根节点而是藏在左子树或者右子树内部。比如一棵树根节点的左子树很深右子树只有一个节点但左子树内部又分出了两个很深的叉那最长的路径就是在左子树内部走完的根本不会绕到根节点再下来。如果只计算“root.left的深度 root.right的深度”你得到的是局部答案而不是全局答案。1.2 直径的准确定义任意两节点间最长路径的边数正经的定义是二叉树中任意两个节点之间的路径所经过的边数最大值就是直径。这里的边数很重要区别于节点数。很多初学者把节点数当边数用结果差了个1又不知道错哪了。举个例子一棵只有一个节点的树节点数是1边数是0所以直径是0。一棵两个节点的树节点数是2边数是1直径是1。这个细节在LeetCode的示例里也有体现它明确用的是边数。如果你习惯用节点数去算最后返回的时候别忘了减1。1.3 为什么“经过每个节点的最长路径”才是关键既然最长路径不一定要经过根节点那我们就换一个思路最长路径必然经过某个节点。这个节点可能是根节点也可能是任意中间节点。而经过某个节点的最长路径实际上就是“这个节点左子树的高度 这个节点右子树的高度”。为什么因为路径是一条连续的线它从某个端点出发向上走到某个最高点再向下走到另一个端点。这个“最高点”就是路径经过的最高节点路径在这里分成两段一段往下走进左子树一段往下走进右子树。所以经过一个节点能形成的最长路径必然是从它左子树的最深节点到它右子树的最深节点长度就是左子树高度加右子树高度。于是问题就转化为遍历所有节点计算每个节点的左子树高度和右子树高度之和取最大值。这个转化是整道题的题眼也是递归解法的理论根基。2. 递归解法把问题拆成左右子树2.1 先写一个能跑通的递归核心我们先明确两件事第一需要一个递归函数来计算某个节点的高度第二需要在递归过程中顺便更新全局的直径答案。高度函数很好写但关键点在于递归函数要返回什么、更新什么。我直接给出最常考的写法Python版本class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.ans 0 def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) self.ans max(self.ans, left right) return max(left, right) 1 depth(root) return self.ans这里depth函数返回的是当前节点的高度同时把left right这个值拿来更新全局最大直径。为什么可以用left right更新因为站在当前节点的视角看从这个节点往左走到最深的距离是left往右走到最深的距离是right那么经过这个节点的最长路径就是left right单位是边数。2.2 逐行拆解运行过程我自己当初学的时候光看代码觉得懂了一动手就懵。后来我把一棵具体的树完整走了一遍才真正明白。就拿一棵简单树举例根节点1左孩子2右孩子3其中2又有左孩子4和右孩子5。递归从depth(1)开始。depth(1)先调depth(2)depth(2)再调depth(4)和depth(5)。depth(4)是叶子节点left depth(None) 0right depth(None) 0此时self.ans max(0, 0 0) 0返回max(0, 0) 1 1。depth(5)同理返回1。回到depth(2)此时left 1right 1self.ans max(0, 1 1) 2返回max(1, 1) 1 2。再回到depth(1)depth(3)返回1。此时left 2right 1self.ans max(2, 2 1) 3。最终返回3。这棵树的直径正是3路径是4-2-1-3边数3或5-2-1-3。2.3 为什么返回的是高度不是直径这是新手最容易卡壳的地方depth函数明明是用来更新直径的为什么最后返回的是高度而不是直径因为上层节点需要的是子树的高度而不是子树内部的直径。如果depth(2)返回的是以2为根的子树直径2那么depth(1)再用left right的时候就全乱了根节点无法知道从2往下还能走多深。打个比方你是一个中间管理层向上级汇报工作时你要汇报的是“我这条线最多还有多少潜力往下挖”而不是“我内部已经完成了多少业绩”。上级要基于你的潜力值再去计算更大的全局路径。2.4 时间复杂度与空间复杂度时间复杂度是O(n)因为每个节点只被访问一次递归函数对每个节点做常数次操作。空间复杂度是O(n)这个n是递归栈的深度。最坏情况下二叉树退化成链状递归深度为n栈开销就是O(n)。平均情况下平衡二叉树的空间复杂度是O(log n)。很多人说递归空间复杂度是O(h)h是树高也对。但面试的时候建议说清楚空间复杂度取决于树高最坏O(n)平均O(log n)这样显得你考虑全面。3. 实操中的运行错误从编译报错到逻辑踩坑3.1 最常见的运行时错误空指针访问“写二叉树程序时为什么总是报运行时错误”——这是很多人搜的热词。答案十有八九是空指针访问。在这道题里最容易犯的错误就是没判空就去访问node.left或node.right。我见过一个典型错误版本def depth(node): left depth(node.left) 1 right depth(node.right) 1 # ...当node是None的时候node.left直接抛异常。你可能觉得“我要访问的节点不是空啊”但递归它不讲情面只要一路递归到叶子叶子再往下一层就是None这时候你不判空运行时错误就来了。正确的做法是在函数开头统一判空if not node: return 0。这一步想明白了这道题的运行时错误就干掉了一大半。3.2 全局变量更新逻辑的坑还有一种运行时错误不报异常但答案是错的。比如有人在递归里这么写def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) return max(left, right) 1 def diameterOfBinaryTree(self, root): depth(root) return left right代码里根本没有left和right这两个变量报错还是小事就算你强行用一个全局变量去接也会因为更新时机不对导致答案偏小。left和right是每次递归的局部变量必须在depth内部就完成self.ans的更新不能等递归结束之后再取因为那个值只代表最后一次递归的状态而不是全局最优。3.3 递归深度过大导致的栈溢出LeetCode上这题的递归深度一般不会触发栈溢出但如果你在本地测试一个极端深的链状树比如自己构造了10万个节点Python的默认递归深度限制大约1000层栈溢出就会发生。遇到这种情况要么调高sys.setrecursionlimit要么改用显式栈做后序遍历的迭代版两者都能将空间复杂度压到O(n)。实际面试中面试官如果追问“如果树很深递归会爆栈你怎么改”你只要答出迭代版后序遍历就能过关。核心是模拟后序遍历的状态栈在出栈时计算左右子树高度并更新答案。3.4 边界输入空树、单节点、纯左子树边界用例一定要单独测。空树root None直接返回0没有任何问题。单节点树depth(root)返回1self.ans仍然是0正确。纯左子树链状比如1-2-3-4递归一路走到底每次left right的最大值出现在倒数第二层答案是3也就是边数3节点数4。很多人在纯链状树上算错因为他们总想着经过根的路径实际上链状树的最长路径就是整条链边数等于节点数减1。我做完这个题后养成了一个习惯每次写完树的题目第一件事就是把空树、单节点、链表树三个边界用例跑一遍。这三次跑完能过滤掉一半以上的隐藏 bug。3.5 排查技巧实录我踩过的三个具体问题问题一返回self.ans前忘了初始化为0。如果树是空树返回的是None而不是0这在LeetCode上直接报类型错误。解决构造函数外直接self.ans 0。问题二用max(left, right) 1还是left right 1搞混。在计算高度时必须用max因为一个节点的高度是它左右子树较高者加1在更新直径时必须用left right因为经过这个节点能走的最长路径是两侧深度之和。一个常用记忆法向上汇报用 max内部结算用 sum。问题三全局变量更新写在返回语句之后。self.ans max(self.ans, left right)必须写在return之前否则递归层层回溯时某些节点的left right就漏掉更新了。写代码时把这个顺序固定下来形成肌肉记忆。4. 变体题目与能力延伸从热题到面试加分项4.1 从“直径”到“最大路径和”负数节点的加入如果你理解了543那么LeetCode 124“二叉树中的最大路径和”就是它的直接升级版。区别在于路径和允许负值所以当你计算某个节点的左侧贡献时如果左子树的路径和是负数你完全可以舍弃它只走右侧。核心代码逻辑变成def dfs(node): if not node: return 0 left max(dfs(node.left), 0) right max(dfs(node.right), 0) self.ans max(self.ans, node.val left right) return node.val max(left, right)你会发现它和直径题的结构一模一样只是把“高度”换成了“路径和”加了一个“负数归零”的处理。所以搞懂543的递归骨架刷124会非常快。4.2 面试追问如何打印出直径的具体路径热题100里通常只要求返回长度但面试官可能会追加一句能打印出这条最长路径吗这时候你需要额外记录每个节点的“左右高度和最大时”的方向。具体做法是维护一个字典或数组记录每个节点左子树和右子树深度之间的选择关系最后根据记录回溯出路径。这个属于进阶玩法不太可能出现在笔试里但如果你在面试中能手写出来绝对是个加分项。我的建议是先用10分钟写出基础递归再用5分钟扩展路径记录时间不够就口述思路。4.3 二叉树直径与图论中“图的直径”的联系热搜词里还有一条“图论中图的直径怎么算”这个跟二叉树直径确实有概念上的联系。图的直径定义为图中任意两节点间最短路径的最大值。二叉树本质上也是一张无向图但它的直径定义更简单因为树上任意两节点之间的路径是唯一的所以“任意两节点的最短路径”就等于它们之间那条唯一的路径取最大值就是树的直径。从图论视角看树的直径有一个经典结论从任意节点出发找到离它最远的节点A再从A出发找到离A最远的节点BA到B的路径就是树的直径。这个结论也能用于二叉树不过实现起来比递归要复杂一些因为需要两次搜索。面试中如果被问到“不用递归怎么做”可以提一下这个图论思路然后实现两次BFS或DFS。4.4 相似题目串联把热题100里的树题串起来热题100里有一批树的题目是共用一个递归框架的。比如“二叉树的最大深度”就是只用max(left, right) 1不更新全局答案“平衡二叉树”是每次算高度后检查左右高度差“直径”是在这个框架上加一个全局最大值。如果把这些题放在一起刷你会发现递归模板变来变去核心就是“返回高度更新答案”。有些人会觉得热题100刷一遍就够了但我个人建议树的题目至少刷两遍。第一遍看着题解写理解递归框架第二遍关掉题解自己从零开始写并且尝试三个以上不同的边界用例。两遍下来你对递归的理解会比刷十道不同类型的题更深。4.5 我在实战中的编码习惯写这道题时我的编码习惯是先在注释里写出递归函数的定义再写函数体。比如我会写# depth(node) 返回以 node 为根的子树的层数高度 # 同时用 self.ans 维护全局最长路径边数注释先行帮我把“返回什么、更新什么”想清楚避免写着写着把函数责任搞混。这个方法对一切递归题都适用强烈建议你也试试。另外本地调试的时候我会写一个简单的测试函数构造几种典型树型root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) print(s.diameterOfBinaryTree(root)) # 期望 3再测空树和单节点。测试通过之后再提交基本上不会出意外。5. 算法之外的思考这道题真正训练的是什么能力5.1 递归函数设计的三问法这道题训练的核心能力是你拿到一个树的问题时能不能快速回答三个问题第一递归函数返回什么第二递归函数做了什么第三全局答案在哪里更新如果这三个问题想不明白刷再多题也只会背模板。以543为例返回的是高度做的是计算左右子树深度并更新最大值全局答案在递归过程中更新。任何一个树形DP问题都可以套这三个问题去拆解。这也是为什么我会把543放在“二叉树的递归模板题”这个分类下而不是当普通题做完就丢。5.2 从刷题到工程递归的思维方式迁移很多人觉得自己不搞算法竞赛刷题没用。但树形递归的思路在工程里其实非常常见。比如解析JSON、构建目录树、处理多级菜单权限、实现评论回复楼层这些场景全都是树形结构。能熟练写出“返回子树信息层层向上汇总”的代码写业务逻辑时处理嵌套结构就会顺手很多。我自己在做一个多级分类树的功能时就借用了这道题的思想每个节点返回自己子树的信息摘要父节点汇总子节点摘要得到全局视图。某种意义上543的递归模式就是分布式思想的单机版。5.3 我和这道题经历的三个阶段我刷这道题其实经历了三个阶段。第一阶段看题解照抄运行通过但内心似懂非懂。第二阶段一周后回头再做发现写不出来卡在“为什么返回的是高度”上。第三阶段把递归的每一层展开画了一遍真正理解“返回什么、更新什么”之后才做到闭着眼能写出来。如果你现在还处于“看了题解觉得懂了但自己写就卡壳”的状态不要焦虑。这很正常唯一有效的办法就是像上面那样手动模拟一两棵具体的树把递归过程在纸上展开走一遍。这个过程做一次胜过看十遍题解。5.4 下一步刷题建议如果你刚做完543下一步我建议按这个顺序继续先做104“二叉树的最大深度”最简单的递归框架入门再做110“平衡二叉树”在深度基础上加条件判断然后做124“二叉树中的最大路径和”把高度换成路径和最后做337“打家劫舍III”树形DP的进阶。这几题连起来刷你会明显感觉到自己的递归思维上了一个台阶。我个人不太建议大家一次只刷一题而是以“递归模板”为单位把同模板的题目打包刷掉这样记忆更牢固。LeetCode热题100其实是很好的一个题目集合里面不少树题都可以这样分包学习。5.5 最后再分享一个小技巧关于“运行时错误”的检测我写树的题目时第一版代码写完不急着提交先在自己脑子里执行一遍最简单的三个案例空树、只有一个根、左链树。空树看返回类型对不对单节点看初始值对不对左链看累加逻辑对不对。这三个案例跑通至少能解决90%的低级运行时错误。如果还有错误就把测试树变小一点打印每个节点的left、right和self.ans的更新过程。比如上面那棵1、2、3、4、5的树你可以看到self.ans从0变成2再变成3的过程核对和手算是否一致。这种debug方式虽然土但对于理解递归来说效果比任何IDE调试器都好。