深入理解二叉树深度：后序遍历、递归与迭代实现详解

二叉树深度的题我见过太多人三分钟秒掉也见过同一个人被追问到沉默。今天聊的这道题来自每日一题系列第16期后序遍历 深度计算。题目本身不复杂无非是求一棵二叉树的最大深度——但围绕这个简单问题能把递归原理、迭代写法、树形DP思想串在一起讲透也能暴露不少刷题时容易忽略的知识盲区。这篇文章想拆清楚一件事为什么计算深度时后序遍历是最自然的解法以及当面试官让你换迭代、换变体、换个问法时你怎么组织思路。适合正在刷二叉树专题的读者也适合准备技术考核但不想靠背模板过关的人。我尽量把理所当然背后的逻辑掰开揉碎顺便把踩过的坑一起说出来。1. 为什么计算深度天生就是后序遍历的活1.1 深度的定义本身就是子问题定义先看一棵二叉树的深度是怎么定义的从根节点到最远叶子节点的路径上的节点数。空树深度为0只有一个根节点的树深度为1。这个定义非常关键它暗示了一种递归拆分方式。如果一棵树的根节点不为空那么整棵树的深度必然等于左子树的深度和右子树的深度两者中较大的那个再加1。写成公式就是depth(node) 0 // node 为空 depth(node) 1 max(depth(node.left), // 非空 depth(node.right))注意这个公式的读取顺序你要算一个节点的深度必须先知道它左右子树的深度。也就是说信息流是自底向上的——先算最底层的叶子再把结果一层层往根上汇总。这种先孩子后自己的处理顺序对应到二叉树的三种遍历方式里恰好就是后序遍历先左子树、再右子树、最后访问自己。1.2 前中后序在深度面前的三张面孔很多人背过一句话前序是根左右中序是左根右后序是左右根。但背下来不等于理解为什么这道题就该用后序。我用下表把三种遍历在深度计算场景下的差异列出来遍历顺序访问自己的时机此时能拿到的信息对深度计算的契合度前序根左右最先访问自己只知道根到当前节点的路径长度不知道子树深度能算但必须带一个当前深度参数自顶向下传中序左根右左子树结束、右子树未开始只有左子树结果右子树信息还没生成不适合直接算深度后序左右根左右子树都处理完左右子树的深度都已就绪最贴合公式和代码都最短这里重点说一下前序。前序不是不能算深度而是它的计算视角是从上往下数层数根节点在第1层往下走一层深度加1走到叶子时记录一个候选值。这种思路需要维护一个函数外的全局变量或者在递归参数里传递当前深度。而后序的视角完全不同它不需要记录当前在第几层它只需要在左右子树各自汇报完高度之后做一次 max 再 1把结果返回给父节点。父节点拿到后继续向上汇总。这就是大多数递归题解只有三行代码的原因因为问题的定义方式决定了遍历顺序。1.3 一棵小树的完整推演光说公式不够直观拿一棵具体的树走一遍递归流程1 / \ 2 3 / \ \ 4 5 6假设现在调用深度递归函数根节点是1。第一步递归进入节点4。节点4没有左孩子也没有右孩子于是 max(0, 0) 1 1节点4返回深度1。第二步节点5同样返回深度1。第三步节点2拿到左右两个孩子的返回值max(1, 1) 1 2节点2返回2。第四步节点6返回1节点3的右孩子深度为1左孩子为空深度0所以 max(0, 1) 1 2。第五步根节点1拿到左子树深度2、右子树深度2max(2, 2) 1 3。最终整棵树的深度是3。注意整个过程中每个节点都是先等左右子树出结果再计算自己这就是后序遍历的推进节奏。你根本不需要刻意写一个后序标志递归函数的天然顺序就是这个。2. 递归解法三行代码与递归栈的心智模型2.1 递归写法不管用什么语言核心代码长这样。我用 Python 演示因为可读性最好class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def max_depth(root): if not root: return 0 return max(max_depth(root.left), max_depth(root.right)) 1如果你更习惯 Java逻辑完全一样public int maxDepth(TreeNode root) { if (root null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; }第一次看这段代码的人容易犯嘀咕为什么一个空节点返回0代码里也没有叶子节点返回1的分支结果却能算对答案是叶子节点不是靠特判算出来的是靠公式推出来的。叶子节点的左右子树都是空left 和 right 两个孩子递归调用都返回0那么叶子节点本身返回 max(0, 0) 1 1。这个1恰好就是叶子节点也算一层的意思。2.2 为什么空节点返回0、叶子节点不用特判这里有一个很重要的约定把空节点的高度定为0。这个约定的好处是递归基只用处理一种情况叶子节点被公式自然覆盖。有人会觉得我加一个 if 判断叶子节点返回1不是更快吗多数情况下没问题但没必要。多写一个判断语句就等于在递归的最底层多做一次条件判断而且容易把基线和空树深度为0的约定搞混。刷题时宁可多信任公式一点把边界条件收敛到最小集合。我见过一种写法在递归函数开头写if not root: return 0 if not root.left and not root.right: return 1这段代码也能跑对但它和空节点返回0 公式推导表达的是同一件事却啰嗦了一圈。面试时如果手写代码我更推荐只留一个空节点判断因为越少的条件分支意味着越难写错。2.3 前序参数版另一种可能为了说明后序为什么好我把前序版本的实现也写出来。用前序思路求深度需要带一个 depth 参数从根往下传def max_depth_top_down(root): ans 0 def dfs(node, depth): nonlocal ans if not node: return ans max(ans, depth) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) return ans这段代码的逻辑是每次进入一个节点就用当前深度去更新全局最大值然后带着 depth 1 继续往下传。整个过程是自上而下的答案不在返回值里而是在外部变量里累积。这个版本和后序版本的核心区别类似于两种工作方式前序版是领导从顶层发指令每到一个层级就记一下这是第几层最后取最大记录。后序版是基层员工先汇报每一层汇总完再往上报最高层拿到的汇总值就是深度。面试时如果你能主动说出这两种思路的区别通常比闷头写代码更有说服力。我自己面试别人时也喜欢问这个点能分清自上而下传参数和自下而上带返回值说明是真的理解了递归而不是背模板。2.4 复杂度分析时间上每个节点恰好被访问一次所以时间复杂度是 O(n)n 是节点总数。空间上递归栈的深度等于树的高度。如果树是平衡的高度是 O(log n)如果树退化成一条链高度就是 O(n)此时递归栈会消耗大量内存。这个递归空间复杂度等于树高的结论经常被拿来追问。所以下面的迭代解法不是炫技是实打实需要掌握的备选方案。3. 迭代解法不依赖系统栈的三种打开方式面试官一句能不能不用递归很多人会当场懵住。原因很简单平时代码都是背着写真到要自己维护一颗栈来代替系统调用栈时思路就容易乱。下面给出三种迭代思路从易到难覆盖不同场景。3.1 栈加深度值最直观的 DFS 迭代第一种思路最简单栈里的每个元素不只是节点还附带该节点对应的深度。模拟递归的前序或后序都无所谓因为我们只关心深度最大值def max_depth_iterative(root): if not root: return 0 stack [(root, 1)] ans 0 while stack: node, depth stack.pop() ans max(ans, depth) if node.left: stack.append((node.left, depth 1)) if node.right: stack.append((node.right, depth 1)) return ans这段代码的核心是当一个节点被弹出时它已经在栈里存好了自己所在的层数。左右孩子入栈时深度直接加1。这里的遍历顺序其实更接近前序变体但因为求的是最大值不依赖严格的左右根访问顺序所以完全够用。这种写法的最大优势是几乎不可能写错。栈不空就循环每弹一个节点就更新 ans然后把孩子压进去。我刷题初期遇到迭代树问题默认先写这个因为它把层数这个关键信息牢牢绑在了每个节点上不会出现绕了一圈忘了深度怎么传的情况。3.2 严格后序的迭代访问标记法问题来了如果题目要求你必须用严格的后序遍历即左子树处理完、右子树处理完、最后才处理当前节点那上面的写法算不算数严谨地说不算。它只是深度计算不是严格的后序序列。真要模拟后序常见做法是给每个节点标记访问状态第一次出栈时不处理先把右孩子、左孩子重新压栈等左右都处理完第二次出栈时才计算当前节点深度。我用一个 Python 版本演示def max_depth_strict_postorder(root): if not root: return 0 depth {None: 0} stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: # 左右子树都已经算完这里才轮到当前节点 depth[node] max(depth[node.left], depth[node.right]) 1 else: # 第一次遇到把自己标成 visited再把右左孩子压栈 stack.append((node, True)) if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) return depth[root]这段代码里dict 相当于一个深度账本key 是节点对象value 是它的深度。栈里存的是 (node, visited) 二元组。当 visited 为 True 时说明它的左孩子和右孩子都已经处理完此时取左右深度做 max 1正好对应后序公式。这个写法体现了用手动栈模拟回溯的精髓代价是代码量明显增加。面试时能在五分钟内写对的人通常对栈的入栈顺序非常敏感。一个容易出错的地方是压栈顺序想让弹出顺序是左、右、根就要反过来压根、右、左。3.3 BFS 层数深度和层数的等价性还有一种思路不看后序直接看层数。树的深度是多少就是有多少层。用队列做层序遍历每处理完一层计数加1最终计数值就是深度from collections import deque def max_depth_bfs(root): if not root: return 0 q deque([root]) depth 0 while q: size len(q) for _ in range(size): node q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) depth 1 return depth这里唯一的细节是在每一层处理循环开始前用 size len(q) 固定当前层的节点数量。如果你在循环里直接写 range(len(q))因为每次 popleft 和 append 都会改变队列长度会一次性多处理或漏处理节点计数器就乱了。BFS 的优点是天然不担心递归爆栈空间复杂度是队列长度最坏情况是最后一层的节点数缺点是代码对层的感知强对子树聚合的感知弱。需要子树间比较的题目比如判断平衡、算直径BFS 往往不如后序顺手。3.4 三种方法怎么选方法代码量是否严格后序突出优点主要风险递归后序最小是表达清晰逻辑最贴近定义大树高时栈溢出栈 深度值小否好写好记不易出错不是严格后序访问标记后序中等是完全模拟后序适合考察原理容易在压栈顺序上写错BFS 层数小否天然防爆栈逐层直观不便于处理子树间聚合我的个人建议是面试先给递归版被追问则优先写栈 深度值。如果面试官明确要求用后序遍历的迭代形式再切换到访问标记法。背两个版本就够了不要贪多。4. 把后序当聚合模板四个同源变体一次讲透很多人刷完最大深度就往下走了其实这道题的价值远不止答案本身。后序遍历的真正威力是一种先收集子树信息再生成父节点信息的聚合模式。抓住这个模式下面这些题都是一网打尽的。4.1 平衡二叉树用 -1 作为失败哨兵判断一棵二叉树是否高度平衡标准定义是每个节点的左右子树高度差不超过1。暴力做法是每个节点都算一次子树高度整体复杂度 O(n²)。后序思路可以一趟完成。核心思想递归函数返回子树高度如果发现某棵子树不平衡直接返回 -1 作为哨兵值父节点看到 -1 就知道整棵树已经不合格。def is_balanced(root): def height(node): if not node: return 0 left_h height(node.left) if left_h -1: return -1 right_h height(node.right) if right_h -1: return -1 if abs(left_h - right_h) 1: return -1 return max(left_h, right_h) 1 return height(root) ! -1这个题和最大深度的关系非常直接它就是在算左右子树深度的过程中顺便做了一次差值的合法性检查。用 -1 而不是 False 的原因是既要传达不平衡这个布尔信息又要传达当前高度这个数值信息一个整数可以同时表达两者省掉了额外的结构体。4.2 最小深度不能直接套最大深度模板最小深度是根节点到最近叶子节点的最短路径上的节点数叶子节点定义为左右孩子都为空。这里有个经典陷阱直接把最大深度里的 max 换成 min得到 min(min_depth(left), min_depth(right)) 1是错的。错在空子树参与比大小。比如一棵只有右子树的链状树左子树为空返回0右子树深3。如果取 min(0, 3) 1结果是1而正确答案应该是 3 1 4。因为空子树这条路径上根本没有叶子节点它不该被当成深度0的路径参与最小化。正确写法要对空子树做引导def min_depth(root): if not root: return 0 if not root.left and not root.right: return 1 if not root.left: return min_depth(root.right) 1 if not root.right: return min_depth(root.left) 1 return min(min_depth(root.left), min_depth(root.right)) 1这个例子很好地说明了一件事模板能帮你省时间但保持对模板语义的理解才能真正不翻车。最大深度和最小深度差一个字代码结构却差了很多根因在于空子树在两种场景下的含义完全相反。4.3 二叉树直径在返回高度的同时更新全局答案二叉树的直径定义是任意两个节点之间路径上的边数最大值。路径不一定经过根节点所以它可能藏在任何一棵子树内部。后序解法是这样的对每个节点经过它的最长路径长度 左子树深度 右子树深度。递归在返回子树深度的同时顺手用这个左深 右深去更新全局答案。def tree_diameter(root): ans 0 def depth(node): nonlocal ans if not node: return 0 left depth(node.left) right depth(node.right) ans max(ans, left right) return max(left, right) 1 depth(root) return ans注意这里我非常喜欢后序的原因只有等左右子树都返回了才能知道经过当前节点的最长路径有多长。如果你用前序走到节点时左右子树的深度信息根本还没生成这个 left right 就无从算起。4.4 N 叉树与更多推广后序聚合模式还能推广到 N 叉树。N 叉树的最大深度就是把左右孩子比较换成所有孩子里找最大def max_depth_nary(root): if not root: return 0 return 1 max((max_depth_nary(child) for child in root.children), default0)关键在 default0它处理了叶子节点的 children 为空的情况。没有这个默认值max 函数面对空序列会直接报错。这一系列变体下来你会发现它们都在做同一件事子树返回结果父节点汇总。想清楚这个模式树相关的题目就不再是零散的知识点而是一套可以复用的思考框架。5. 刷题和面试里最容易翻车的四个细节5.1 口径要对齐空树的深度是0还是1这是一个很容易被忽略的约定问题。有的教材把根节点深度为0那么叶子节点深度就是树高减1而刷题场景里通常约定 root 为 null 时深度是0最好的做法是在写代码前明确问一句。如果你在面试现场直接说我按空树返回0的口径来写这句话既能体现边界意识也能避免和你后面代码的不一致。闷头写然后又改来改去才是面试官最不愿意看到的。5.2 递归爆栈退化树的隐藏风险极端情况下一棵二叉树可以退化成链几千层深。很多语言的递归深度是有限制的比如 Python 默认递归深度大约在1000层左右超过会抛 RecursionError。刷题用例通常不会这么极端但我在实际处理大规模数据时确实撞到过。如果明确知道树可能很深最稳妥的做法是用迭代版本。不要依赖 sys.setrecursionlimit 去硬撑那只是把炸点往后挪了挪不是真正的解决方案。5.3 迭代里的 None 与动态 length 陷阱迭代写法里有两个非常具体、极易踩的坑。第一个是把 None 孩子压入栈或队列。在栈 深度值的写法里如果压入了 None弹出时会因为尝试访问 None.left 而报错在 BFS 里None 混入队列会打断每层处理固定数量节点的逻辑。第二个坑在 BFS 里更隐蔽while q: for _ in range(len(q)): # 错误示范len(q) 在循环中不断变化 node q.popleft() ...每轮 popleft 和 append 都会改变 len(q)导致循环次数被动态重算。正确做法是入循环前先用 size len(q) 固定本层数量。这个错误非常容易犯因为它不报错只是结果悄悄变错。5.4 全局答案的写法从 nonlocal 到可变对象凡是需要遍历过程中更新全局答案的题目比如二叉树直径、前序版本的最大深度都会遇到一个问题怎么在递归内部修改外部变量。Python 里最常见的是 nonlocal 关键字也可以用列表比如 ans [0]然后在递归里用 ans[0] max(ans[0], ...)。Java 里可以用成员变量或者 int[1] 数组。这里有个容易犯的低级错误有些人把 ans 直接当递归函数的普通参数传下去然后在里面赋值以为外层能看到。实际上普通参数是按值传递改了也传不回来。我在代码评审里见过好几次这种问题建议第一反应就使用 nonlocal 或可变容器。一点自己的收尾体会刷树相关的题目刷到中期我养成了一个习惯遇到树先问自己一句这道题的答案是要从叶子向上汇总还是从根向下传参想清楚这一句后序还是前序、递归还是迭代都不用再纠结了。后序遍历 深度计算这道每日一题#16本身代码量少得可怜但它牵出的递归心智模型、迭代栈模拟、树形DP雏形是一整条知识线。把这根线捋顺了后面再遇到平衡树、最近公共祖先、树上的路径统计都会顺畅很多。