手写递归满天飞但能把“二叉树的直径”这道题一次写对的人真没那么多。很多人在面试里拿到这道题第一反应是“找根节点左右子树的高度加起来”然后洋洋洒洒写了个深度函数一跑测试用例发现答案不对——问题就出在“直径不一定经过根节点”这个隐藏条件上。这道题本质上是树形动态规划的入门模板与其说是考递归不如说是考你对后序遍历返回值含义的理解。我用一篇文章把这道题的完整思考链路、代码细节、踩坑点和变式题目一次说清你可以直接拿去参考。1. 题目理解与破题思路1.1 先搞清楚题目到底在求什么力扣原题说的是给你一棵二叉树的根节点返回这棵树的直径。直径的定义是“任意两个节点路径长度中的最大值”路径长度按边数计算。这句话有三个关键点需要拆开看第一路径的起点和终点是“任意两个节点”不是限定在左右子树里各挑一个也不是必须包含根节点。很多人第一次做这题就把路径理解成“从根往左走到某个叶子再往右走到某个叶子”于是直接算leftHeight rightHeight。这个思路运气好能过一半测试用例但只要出现一条完整路径藏在某个子树内部、压根不经过根节点的情况结果就错了。第二长度按边数算。两个相邻节点之间的路径长度是1单个节点的路径长度是0。这个细节决定了叶子节点的高度返回0而不是1也决定了最终答案的初值应该设成0而不是1。第三直径可以退化。如果整棵树只有一个节点没有边那直径就是0如果树是一条链直径就是链的长度。空树的情况力扣一般不会给但写代码时要防御好。1.2 核心思路一个关键等式树的递归天然带有“自底向上汇总信息”的特点。对于任何一个节点它作为路径“最高点”也就是路径拐弯的地方能形成的最大路径有多长假设当前节点为 cur它左子树的最大高度是 L右子树的最大高度是 R那么经过 cur 拐弯的路径长度就是L R。为什么要用“高度”而不是“深度”因为高度是以当前节点为起点向下能走到的最大层数正好对应“从 cur 往左走的最远边数”加“从 cur 往右走的最远边数”拼起来就是以 cur 为拐点的最长路径。那整棵树的直径怎么算就是遍历所有节点把每个节点作为拐点时的L R都算一遍取最大值。这个思路等价于一个非常优美的等价命题二叉树直径等于所有节点中左子树高度与右子树高度之和的最大值。关键就在这里路径不一定经过根节点但路径一定“经过”某个节点作为拐点。路径上总有一个位置是“从上升变成下降”的这个位置在递归里就是我们要检查的节点。所以只要每个节点都检查一遍以它为拐点的路径就一定能覆盖全局最长的那条路径。1.3 为什么用后序遍历而不是其他遍历这题只能用后序遍历不能用前序和中序原因是信息流向决定的。前序遍历先处理当前节点再递归子树可问题是你根本不知道子树长什么样没法在当前节点算出L R。中序遍历同理处理当前节点时右子树还没访问。只有后序遍历先把左右子树都递归完整拿到左高度和右高度之后再回头处理当前节点这时信息才齐。所以这个“先子树、后自己”的顺序天然匹配了“子树返回信息父节点汇总信息”的树形DP模式。可以说所有这类“子树信息决定父节点答案”的题目面试时都优先往后序遍历想不用怀疑。2. 递归核心实现与代码细节2.1 写一个最小可用版本先看一个最简洁的 Python 实现我们基于它展开所有细节class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.ans 0 def height(node): if not node: return 0 left height(node.left) right height(node.right) self.ans max(self.ans, left right) return max(left, right) 1 height(root) return self.ans这段代码只有十几行但它包含了三个关键设计决策用全局变量self.ans存直径、用height函数返回子树高度、在返回高度之前先更新答案。这三个决策分别对应不同的知识点我一个个拆开讲。2.2 全局变量 vs 返回值层次分明的变量设计很多初学者会问self.ans能不能直接作为返回值的一部分一起返回能但要小心因为height函数的返回值会被父节点当作“该子树高度”来用它必须是一个纯粹的高度值不能混入直径信息否则上层算高度时就会出错。一个好的设计原则是返回值负责向父节点传递“我作为子树能提供的高度”全局变量负责收集“所有候选答案里的最大值”。两者职责不同谁也不替代谁。这也是一些解法里会用max(leftDepth rightDepth, leftResult, rightResult)这种三参数比较方式的原因。那种写法把子树的直径也作为返回值传上去逻辑上更“纯函数”但写法上更啰嗦而且容易在返回时漏掉比较条件。全局变量的写法在工程上更常见也是面试官最容易接受的那一种因为它直观地体现了“递归遍历 边遍历边收集答案”的模式。如果你担心多线程之类的问题可以在内部函数上用nonlocal声明一个外部变量效果一样。我用 Python 写的时候喜欢直接用self.ans因为类属性在多次调用时记得手动重置而nonlocal用法更干净二者选一个顺手的一致用就好。2.3 关键代码逐行拆解先看递归基if not node: return 0空节点没有子节点它的高度是0。这个0不只是高度值也是递归能够终止的基石。再看左右递归left height(node.left) right height(node.right)这两行的时间顺序很微妙它们先执行然后才轮到用它们。也就是说程序会先把左右子树彻底递归到底一层层返回上来才执行下面的两行代码。这个执行顺序就是后序遍历的顺序是理解全代码的钥匙。然后是答案更新self.ans max(self.ans, left right)left right是以当前节点为拐点的最长路径边数。为什么不用加1因为 left 和 right 已经是“边数”left 表示从左孩子往下最远能走的边数right 同理它们加起来就是从左子树最远点一路走到右子树最远点的边数。举个例子某个节点左子树高度3右子树高度4则从左子树最深处到右子树最深处一共要走 3 4 7 条边即经过7条边。中间那个拐点自身不算边。最后是高度返回return max(left, right) 1这里加的这个 1代表当前节点到它的某个子节点之间那条边。这个加1非常容易跟left right里的边数搞混我见过不少人在返回语句里漏掉加1导致整个递归全都返回0最终 ans 永远是0连最简单的用例都过不了。所以建议你在返回之前心里默念一遍当前节点向上提供给父节点的高度等于左右子树中更高的一侧高度再加上连接父子的那一条边。3. 复杂度分析与边界情况3.1 时间复杂度与空间复杂度遍历整棵树每个节点都只访问一次每次做常数时间的比较和加法所以时间复杂度是 O(N)N是树节点数。这个复杂度已经是最优了因为直径至少要找到最远的那对节点而找任何“最远”信息大概率要遍历全树。空间复杂度是递归栈的深度。递归函数height每递归一层就占用一层调用栈最多递归到树的高度层。所以空间复杂度是 O(H)H 是树高。最坏情况下树退化成一条链H N空间 O(N)平衡树情况下 H logN空间 O(logN)。这个空间的伸缩性也是递归实现需要注意的后面在栈溢出部分我再展开。3.2 容易踩坑的几个边界场景第一种空树。代码里height(root)会直接进not node分支返回0self.ans保持初值0。如果严格按“直径按边数算”的定义空树返回0完全正确。有些题目变体如果问“求路径上的节点数”空树要返回0单个节点要返回1别搞混。第二种单节点树。只有一个根节点时left和right都是0left right 0ans更新成0返回max(0, 0) 1 1。这个过程其实告诉你一件事树的高度和树的直径在很多情况下是两码事。单节点树高度是1按层数算直径却是0按边数算。第三种斜树退化链。比如一条 1 - 2 - 3 - 4 的链。递归会一路走到最深的4然后一层层返回。每个节点的左右子树中必有一侧为0所以每个节点的left right就等于它的深度从下往上数整条链的最大直径出现在根节点值是3。斜树的情况最容易验证你的代码逻辑因为它把“沿单侧走”和“左右拼接”两种模式都覆盖了。第四种形状对称但答案不对称的树。比如一棵树左子树很深而右子树很浅但最长的路径发生在左子树的内部不经过根。如果你只算根的左右高度和一定会算错。这种用例可以自己构造一下左子树的右子树特别深根节点右子树只有一个节点。正确答案是左子树内部那条长路径的边数而不是左深度加右深度。3.3 边界值在面试中的隐形考察点面试题看起来很基础但面试官非常喜欢追问“如果树特别深怎么办”这其实是在考察你是否知道递归深度可能超过Python默认的递归上限。Python默认递归深度是1000层左右如果树的高度超过1000递归实现就会抛出 RecursionError。面试中一般不会真给那么深的树但你能主动说出来“递归实现的空间复杂度是O(H)深度过大时可以考虑迭代后序遍历用显式栈代替系统调用栈”面试官对你这题的印象分完全不一样。迭代写法我不建议现场写除非你被明确要求。但思路可以说使用栈做后序遍历记录每个节点的状态等左右子树都处理完后再更新高度和 ans。逻辑上和递归完全一致只是把系统栈换成显式栈能抗住的深度更大代价是代码复杂度上升不少。4. 常见错误与调试实录4.1 误区直径一定会经过根节点这是我见过频率最高的错误。做法是把题目理解成了“左子树最大深度 右子树最大深度”然后只算一次根节点不遍历所有节点。它在这样一种树上必然错根节点左子树内部存在一条很长的路径而根的右子树很矮导致根处的左右高和小于左子树内部的路径长度。正确的脑子里的模型应该是每一个节点都可能是拐点所以要检查所有节点的 left right而不是只检查根节点。从“经过某个拐点”的视角去理解就再也不会忘记在递归里更新 ans 了。实测几个用例就知道对稍微复杂的树只做根节点一次拼接的答案会明显偏小。我建议你自己构造一棵“左子树的右子树很深”的树跑一下代码亲眼看到答案比左高右高大这个误区才算真正破了。4.2 误区返回值写错导致答案被翻倍或恒为0两个典型错误。第一返回max(left, right) 1忘写1。所有高度返回0ans 永远是0测什么都不对。这个错误从某些症状上看像是“代码逻辑没错但结果恒0”其实卡在return语句上。排查方法很简单打印每个节点的 left 和 right如果全都是0基本就是返回忘了加1。第二返回left right 1。这种写法会把“以当前节点为拐点的路径长度”当成高度传给父节点导致父节点在计算时把子树的直径和高度混在一起最终答案会被放大或重复计算。记住返回给父节点的一定是高度不是路径长度。4.3 用最小用例快速验证自己的答案写完之后一定要自测别直接交。我一般会建下面几个用例花不了30秒表格里列清楚组别、树的形状、预期直径一眼对照测试组树的结构预期直径说明用例一空树0边界防御用例二单节点0按边数计算的边界用例三三个节点链2简单链最容易看逻辑用例四根有两个子节点每个子节点又各带一个子节点2平衡小树用例五左子树内部一条长路径右子树很矮应为左子树内部路径长度专治“只算根”的错误4.4 调试技巧打印递归过程如果用例没跑过最直接的方法是加打印。我通常打印当前节点值、left、right、更新后的ans、返回值就能立刻看到递归的每一层发生了什么。比如def height(node, depth0): if not node: return 0 left height(node.left, depth 1) right height(node.right, depth 1) print( * depth, node:, node.val, L:, left, R:, right, candidate:, left right) self.ans max(self.ans, left right) return max(left, right) 1这样一个节点一个节点看过去逻辑错误通常一眼就暴露了。打印的缩进还能直观看出递归的深度顺序。调试完记得删掉打印别留在提交代码里。5. 变种题与扩展思考5.1 变体一求路径经过的节点数力扣原题问的是边数但很多手撕代码环节会把问题改成“求直径路径的节点总数”或者干脆把原题中的路径长度定义改掉。此时核心改动在加1的位置self.ans max(self.ans, left right 1) return max(left, right) 1区别是什么原版的left right是把两个边数相加路径长度等于边数节点数版本里拐点本身也要计入所以要加1。但是注意left 和 right 如果按高度算本来就是节点数减一的关系所以最终路径总节点数 left right 1。有些教材里高度定义成节点数而非边数那公式又不一样做题前先确认好久题目定义的是边还是节点别一上来就套模板。5.2 变体二输出最长路径本身有些题目不满足于只输出长度会让你返回具体的路径节点或节点值列表。做法是维护一个局部变量记录当前最优路径的两个端点self.best_left None self.best_right None self.best_len 0 def height(node): if not node: return 0, node # 高度以及当前子树最深的叶子方向 ...如果left right大于当前best_len就更新两个端点。最后整棵树的直径路径就是从 best_left 到 best_right 的路径。输出路径需要单独写一个求两个节点之间路径的辅助函数或者利用记录下的拐点做扩展。这个变体在面试里属于进阶追问能当场写出来的人不多练熟原题之后可以试试。5.3 变体三带权边的直径如果每条边有权重问题变成求加权路径最大值。思路一模一样只是在递归返回高度时加的不再是固定的1而是对应边的权重return max(left weight_left, right weight_right)这里有个小陷阱如果边的权重可能为负数max(left, right) 1这种写法就不成立了因为负数边会让“更高”的判断失效你需要改成分别计算“经过该边的最佳贡献”。不过在实际面试中边权为负的二叉树直径很少出现知道怎么改就行。5.4 变体四多叉树或者图结构二叉树只是树形DP的入门载体。把节点扩展成任意多叉树思路一样如果扩展成图找直径就变成了两遍 BFS/DFS 或者 Floyd 之类的算法那是另一个话题了。核心启示是只要信息能从子树汇总到父节点后序遍历 全局答案收集这套模式就能复用。最后再分享一个小技巧这道题真正难的不是代码而是建立“每个节点都是候选拐点”的思维模型。以后再做任何“树上的最长XX”类题目先问自己三个问题信息从哪些子树来当前节点如何汇总汇总结果是否参与全局最优答清楚这三个问题代码基本就出来了。我自己刷树形DP题目时一直用这个套路从二叉树直径到监控二叉树效率都很高。另外反复强调一句提交之前一定要跑边界用例空树、单节点、斜树、左右失衡树四类用例全覆盖基本就没问题了。
