二叉树直径怎么算？后序遍历与递归返回值设计详解

如果你刷过二叉树相关的题大概率遇到过“二叉树的直径”这道经典题。它表面上叫直径实际上问的是在二叉树里随便找两个节点它们之间那条唯一的简单路径最多能经过多少条边。这个答案可能藏在左子树里可能跨过根节点也可能只存在于某一棵子树内部所以只靠“从根往下找两条最长分支”的思路很容易栽跟头。这篇我会从定义开始把为什么用后序遍历、递归到底该返回什么、哪里容易报运行时错误讲清楚适合刚把遍历和深度吃透、准备开始啃树形 DP 的读者。1. 一颗二叉树的“直径”到底在问什么1.1 先厘清定义是边数不是节点数LeetCode 543 的原题描述说得很简单给定一棵二叉树你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值这条路径可能穿过也可能不穿过根结点。注意这里的“路径长度”指的是边的数量不是经过的节点数量。很多初学者第一眼会误以为是在求“树的最大宽度”或者“最左叶子到最右叶子的距离”其实都不准确。举个例子一棵长这样的树1 / \ 2 3 / \ 4 5节点 4 到节点 3 的路径是 4 - 2 - 1 - 3一共 3 条边节点 4 到节点 5 的路径是 4 - 2 - 5一共 2 条边。所以这棵树的直径是 3而不是 2。如果按“节点数”去数很容易数出 4 来但题目要的是边数这是第一个必须刻进脑子里的差异。还有两个边界情况要提前约定空树没有节点直径是 0只有一个节点的树直径为 0。这两个边界在递归实现里天然会被处理但你写测试用例或者和面试官确认需求时最好先明确避免后面浪费时间。1.2 为什么这道题值得单独拎出来讲“二叉树的直径”表面上是树的遍历题本质却是“树形 DP”的入门题目。所谓树形 DP就是在一个树结构上做动态规划每个节点根据子树返回的信息计算出当前节点的某个指标同时维护一个全局最优解。这道题刚好把这个模式体现得淋漓尽致递归函数只负责向上传递“子树高度”而直径另开一个全局变量不断更新。更实际的原因是它和你刷过的很多题都有关联。比如“二叉树的最大深度”——很多人的第一版代码就是先写一个求深度的函数再对每个节点计算左右子树深度之和取最大值。这种写法没有错但会重复遍历复杂度从 O(n) 变成 O(n^2)。如果你能理解本文推荐的后序 全局变量的写法那么“平衡二叉树”“二叉树中的最大路径和”这些进阶题你都会顺很多。适合读这篇的人一是刚学完二叉树递归遍历想练手但总卡在递归返回值设计上的二是在面试里被问到这题能背出代码但解释不清为什么的人。后者其实更危险因为面试官最喜欢追问一句“你为什么要用后序返回值为什么是这个”2. 核心思路把“直径”问题拆成“深度”问题2.1 一个关键观察每条最长路径都有“拐点”任意一条二叉树里的路径都是从一个节点网上走再往下走到另一个节点。由于树上两个节点之间只有唯一一条简单路径这条路径上一定有一个距离根节点最近的节点我习惯叫它“拐点”。路径在这个拐点处从“向上”变成“向下”整条路径可以拆成两段从拐点左子树里的某个节点一路向上到拐点再从拐点一路向下到右子树里的某个节点。举个例子路径 4 - 2 - 1 - 3 的拐点就是 1左边依赖节点 2 的高度右边依赖节点 3 的高度。路径 4 - 2 - 5 的拐点是 2它左右分别依赖节点 4 和节点 5 的高度。所以如果对于每一个节点我们知道左子树的最大深度 leftDepth 和右子树的最大深度 rightDepth那么经过这个节点的最长路径长度就是 leftDepth rightDepth。你只需要遍历所有节点取这个和的最大值就是整棵树的直径。为什么“拐点”一定是路径上离根最近的节点因为如果拐点不是离根最近的节点那路径会先往上越过它这样路径上就会存在一个更靠近根的分叉点矛盾。这个观察是整个算法的基石理解了它代码就是顺理成章的事。2.2 为什么必须是后序遍历很多人在初学递归时习惯性先处理当前节点再递归子节点这是先序遍历。但对于直径问题先序是错的你处理当前节点时根本不知道左右子树有多深自然算不出 leftDepth rightDepth。后序遍历的顺序是“左子树 - 右子树 - 当前节点”每一步都保证了子节点的信息已经就绪。你只需要在“回到当前节点”这一步做两件事更新全局直径答案、向父节点提交当前子树的高度。一句话概括当前节点的答案依赖子树的答案所以必须自底向上算这就是后序。如果你习惯层序遍历BFS当然也能做先把所有节点按层存下来然后从下往上处理每个节点。但那样需要额外的空间和反向下标映射代码明显比递归后序复杂。面试场景下递归后序是首选在工程场景里如果担心递归爆栈再考虑迭代后序。2.3 返回“深度”记录“直径”这里是最容易纠结的地方。递归函数到底返回什么很多人的第一反应是“返回以当前节点为起点的最长路径长度”。这不是不行但会让代码变得很绕。更清晰的做法是递归函数只返回“当前子树的最大深度”让直径通过一个外部变量来更新。深度怎么定义我们采用最方便的约定对于叶子节点它的深度为 1空节点深度为 0。那么一个节点的深度就是 max(左子树深度, 右子树深度) 1。这个 1 就是自己和子节点之间那条边的计数。这样算出来的是“从当前节点出发最多能往下走几条边再回到自己或者说携带多少个节点”虽然严格说叫“高度”更准确但刷题语境里大家都习惯说“深度”跟着用就行。至于 leftDepth rightDepth 为什么就是经过当前节点的最长路径边数因为左边贡献的是一条从叶子网上走的路径长度右边贡献的是一条从当前节点往下的路径长度两者拼接起来总边数正好相加。例如节点 2 的左子树深度 1、右子树深度 1相加得 2对应路径 4-2-5 的两条边。至于直径因为递归函数只能向上返回一个值如果想把“以每个节点为拐点的最优值”都带上去就得用另一个公共变量。LeetCode 的 Python 写法常用 self.ans在 C 里可以用引用参数或者类成员变量。3. 代码实现与调用栈推演3.1 Python 实现带注释这里直接给出一个最干净的后序递归版本。from typing import Optional # Definition for a binary tree node. class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.ans 0 def dfs(node: Optional[TreeNode]) - int: if not node: return 0 left_depth dfs(node.left) right_depth dfs(node.right) # 在当前节点“拐弯”的路径长度 self.ans max(self.ans, left_depth right_depth) # 当前子树能提供的最大深度 return max(left_depth, right_depth) 1 dfs(root) return self.ans这段代码有几个细节需要解释。第一if not node: return 0是递归终点对应空节点深度为 0。如果这里写return 1或者忘了写整个递归会乱套要么叶子深度变成 2要么递归不终止。第二self.ans max(self.ans, left_depth right_depth)必须在递归左右子树之后因为此时 left_depth 和 right_depth 才是有效值。第三最终返回值是max(left_depth, right_depth) 1不是left_depth right_depth 1。很多初学者在这里写错把“当前子树能贡献的深度”写成了“左右子树深度之和”这样父节点拿到的深度就会被严重放大。还有一个小陷阱Python 里如果在dfs内部直接ans ...会创建一个局部变量和外层self.ans没有关系。所以要么用self.ans要么在 Python 3 用nonlocal ans。用self.ans是最不容易出错的写法。3.2 手工推演一棵三层小树光看代码还是有点抽象我用手推一遍。就以上面的树为例1 / \ 2 3 / \ 4 5调用入口dfs(1)进入后先递归左子树。dfs(2)进入先递归左子树dfs(4)node 不是空左右都是空left_depth 0right_depth 0。self.ans max(0, 0) 0。返回 max(0, 0) 1 1。dfs(5)同理返回 1。回到dfs(2)left_depth 1right_depth 1。self.ans max(0, 1 1) 2对应路径 4-2-5。返回 max(1, 1) 1 2。dfs(3)左右都为空self.ans 保持 2返回 1。回到dfs(1)left_depth 2right_depth 1。self.ans max(2, 2 1) 3对应路径 4-2-1-3。返回 max(2, 1) 1 3。最终dfs(root)执行完self.ans 3返回 3。注意最后dfs(1)返回的 3 已经没人用了因为我们只关心 self.ans 的结果。这正是“返回值和最终答案分离”的体现返回值是给父节点用的局部信息self.ans 是给整棵树用的全局结果。3.3 复杂度与判题细节时间复杂度很好分析每个节点恰好访问一次递归中每个节点做的事是常数次操作所以是 O(n)n 是节点数。空间复杂度取决于递归调用栈的深度最坏情况是树退化成一条链递归深度为 n空间 O(n)平均/最好情况也就是平衡树空间 O(log n)。在 LeetCode 上这个方法名和参数都是固定的你不需要处理输入输出。要注意的是如果你的代码里没有在diameterOfBinaryTree开头把self.ans初始化成 0而上一道题的测试用例已经把某个解法的self.ans改变了那么同一个 Solution 实例在多个测试用例之间可能会出现结果互相污染。这一点在第 4 节里展开说。4. 常见坑为什么写二叉树程序总是报运行时错误4.1 空指针/None 处理最经典也最阴险二叉树递归代码最常见的运行时错误就是AttributeError: NoneType object has no attribute left。写错的方式一般是这样的def dfs(node): # 如果漏了判空直接访问 node.left left dfs(node.left)当 node 是叶子节点时node.left 是 None但上面的dfs在下一层会尝试访问None.left于是炸了。解决办法很简单在函数开头加if not node: return 0。这个判断同时承担了“空子树深度为 0”和“递归终止”两个职责。还有一种更隐蔽的判空条件是if node is None这没问题但有些人会把叶子节点的返回写成return 1导致实际计算时所有深度都多 1。这个问题不会立刻报错但答案总是偏大。怎么自查单节点树直径应该是 0如果跑出来是 1 或 2那一定是深度定义或返回值设计乱套了。4.2 递归深度爆栈LeetCode 里“运行时错误”的头号元凶很多人一听到“写二叉树程序老是报运行时错误”第一反应是代码逻辑错了。但有一种情况逻辑完全正确OJ 依然给你一个RecursionError或者AddressSanitizer: stack-overflow。原因就是递归深度太大了。Python 默认递归深度限制大约是 1000。如果二叉树退化成一条 1000 层的链后序递归就会在这一层直接崩溃。Locally test 小的树完全没问题一上线就挂特别折磨人。排查方法很简单先看树高。如果可能超过数百层就要考虑改用迭代写法。LeetCode 543 的标准测试用例通常不会刻意刁难到这个程度但你自己写本地测试时经常会构造出深链或者你在面试中白板写代码时面试官会追问“如果树很高怎么办”。这时候你可以说可以用栈模拟后序遍历把递归展开成迭代或者用 Morris 遍历的空间优化方案。这些我会放到后面一篇“二”里细讲。如果只是临时想在本机跑也可以这样import sys sys.setrecursionlimit(100000)但请注意这只是把问题延后不是解决。递归深度超过几万时依然会栈溢出而且很多编程环境不允许你修改递归限制。工程上更稳妥的做法是迭代。4.3 全局变量在多个测试用例间互相污染用self.ans保存直径有一个隐藏的坑。如果你在一个类里写了多个方法或者你的diameterOfBinaryTree被反复调用而self.ans没有在方法入口处重置就可能出现上一个用例的结果污染下一个用例。举个例子class Solution: def diameterOfBinaryTree(self, root): # 忘了 self.ans 0 def dfs(node): ... dfs(root) return self.ans如果self.ans是一个类变量或者上一次调用结束时留了一个很大的值第二次调用时max就会取到那个旧值答案错误。正确的做法是在函数入口第一时间self.ans 0。我遇到过有人把ans定义成全局变量ans 0在函数内直接读它这样可以但一旦涉及模块间的并发或者多次运行就非常容易出问题。笔试 OJ 一般每次会重新实例化 Solution所以很多侥幸通过的代码其实是不安全的。你自己的工程代码里尽量不要用模块级变量存这类中间状态。4.4 常见问题速查表症状根本原因解决方案AttributeError: NoneType object has no attribute left递归入口没有判空函数开头加if not node: return 0RecursionError: maximum recursion depth exceeded树高超过递归限制改迭代后序或临时调高递归限制答案偏大单节点树结果不是 0深度返回逻辑写错叶子返回了错误值检查return max(left, right) 1同一代码多个用例一起跑时会出错self.ans没有重新初始化在diameterOfBinaryTree入口处重置答案偏小始终等于某个子树内部的直径没有在递归中途更新 ans只在返回前更新确认self.ans更新位置在递归左右子树之后5. 由直径延伸遍历、深度、搜索二叉树与线索二叉树5.1 直径和深度是“血脉相连”的如果你已经熟练掌握了“二叉树的最大深度”那么理解直径会非常快。求深度是对每个节点取左右子树的深度的较大值再加 1。求直径是对每个节点把左右子树的深度加起来再取全局最大值。差别只有一行代码一个是max一个是sum。这个模式太常用了我把它们当成同一个模板来记先递归左子树 先递归右子树 利用左右返回值更新当前答案 向上返回一个供父节点使用的局部值。这不是某个特定题的技巧而是“树形 DP”的通用套路。“二叉树的最大路径和”就是在这个模板上把“深度”换成“路径和”“判断平衡二叉树”就是把“深度”和“是否平衡”打包成元组返回。所以直径这道题真算得上树形 DP 的敲门砖。5.2 四种遍历方式在直径计算中的角色前面说了后序遍历是最自然的。但你可能会想前序和中序是不是完全不能用也不是只是需要额外手段。比如先序遍历时我们可以在遇到节点时先去递归子节点这其实变成了另一种“模拟后序”的写法。真正的关键在于“先拿到子结果再处理父节点”顺序不限。层序遍历BFS也可以做思路是先按层得到节点序列然后从最后一层向上处理每个节点。每个节点的深度可以由其子节点深度计算直径也在这一过程中更新。BFS 的缺点是需要记录父子关系和层序代码长度会翻倍。面试时如果能流畅写出递归后序版本就已经足够拿满分了BFS 版本更适合作为“我对空间复杂度有更多思考”的加分项来聊。5.3 在搜索二叉树里直径会变简单吗有读者可能会想既然是搜索二叉树BST左小右大有性质直径能不能直接用“最左节点到最右节点”的距离答案是不行。BST 只规定了节点值的大小关系没有规定树的形态。一棵 BST 可能长成左子树很深、右子树很浅的样子最左节点到最右节点的距离不一定就是直径因为可能出现“左子树的某个内部叶子到右子树另一个内部叶子”更长的情况。用一个反例根节点是 10左孩子是 9左孩子的左孩子是 8一直套成一条左斜链右子树只有一层。此时最左到最右的路径确实很长但直径也可能就在这条左斜链内部。所以 BST 的性质对求直径没有本质帮助该算的深度一分都不能少。这也是为什么这题在所有二叉树上都用同一个解法。5.4 线索二叉树与直径如果你了解“线索二叉树”应该知道它的核心目的是在不借助栈和递归的前提下用空指针记录前驱、后继从而高效地进行中序遍历。但线索只解决了“遍历顺序”问题并没有给你“子树深度”这个信息。直径的计算需要的是左右子树的深度而不是线性遍历顺序所以线索化并不能直接简化直径计算。不过线索二叉树的“反向”思路倒是值得借鉴如果你不想用递归又不想显式建栈可以用 Morris 遍历的方式把树临时改造成线性结构再模拟后序计算。这个思路在“二”里面我会展开讲它能在 O(1) 额外空间里求出直径算是一个让面试官眼前一亮的进阶版本。6. 实操心得与系列预告我个人在实际操作中的体会是二叉树的直径是一道“会了模板就会一类题”的典型代表。很多刷题者容易把它当成一道孤立的递归题去背背完就忘。其实更好的方式是把“递归返回值设计”和“外部变量更新答案”这两个动作刻进肌肉记忆。每次拿到树相关的题先问自己三个问题我需要从子树拿什么信息当前节点如何用这些信息父节点需要我怎么向上汇报想清楚这三件事代码基本不会错。最后再分享一个小技巧调试这类递归时别只盯着最终结果可以在每一步递归入口打印节点值和当前左右深度。我在本地经常用这样的临时日志node2, left_depth1, right_depth1, ans2 node1, left_depth2, right_depth1, ans3一眼就能看出答案是在哪个节点被更新的比自己干想快很多。这篇是“一”我把 IO 的标准版、后序思路、常见运行时错误都讲透了。后续的“二”准备聊迭代后序如何写、Morris 风格的低空间复杂度解法以及“二叉树的最大路径和”等几个同源题目怎么套用同一套模板。你可以先用这篇的代码多刷几道相似题等递归版本写熟了再去看进阶内容不迟。