二叉树遍历全解析：中序与层序，从DFS到BFS的代码模板-北京尧图网络

1. 为什么这两道遍历题值得反复刷穿刷题刷到树这一块的时候LeetCode上94题二叉树的中序遍历和102题二叉树的层序遍历几乎总是被放在一起推荐。一个走深度方向递归到底一个按层横向逐层扫描看起来风格完全不同——但把这两道题并到一起刷恰恰能帮你一次理清**DFS深度优先搜索和BFS广度优先搜索**这两大遍历体系。如果你正在准备算法面试或者刚开始系统学数据结构这两道题值得刷到形成肌肉记忆因为后续一大票树的题目——二叉搜索树第K小、锯齿形层序、右视图、每层最大值——本质上都是这两段代码的变体。先看一眼题目要求94. 二叉树的中序遍历给定一棵二叉树的根节点按左子树、根节点、右子树的顺序返回节点值的列表。102. 二叉树的层序遍历给定一棵二叉树的根节点按从上到下、从左到右的顺序逐层返回节点值组成的二维列表。两道题都不涉及复杂的算法技巧纯粹考你有没有把遍历这件事理解透。但恰恰是这种基础题面试时翻车率极高——很多人能默写出递归版本一问到迭代版本就卡壳层序遍历用队列能写出来一换个输出格式比如Z字形遍历就不知道怎么组织结果。这篇文章我会把两道题的原理拆开揉碎从递归到迭代从BFS标准模板到高频变体最后再聊一聊为什么很多人写二叉树程序总是报运行时错误——这些坑我基本都踩过希望能帮你省一点时间。2. 中序遍历递归之外的迭代路线藏着树的本质2.1 递归版本为什么是标准答案但面试官不想只听这个二叉树遍历的递归实现是初学阶段最先接触的东西。中序遍历的递归写法很简单def inorder_traversal(root): res [] def dfs(node): if not node: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return res代码只有几行但背后隐含的是递归栈的概念每往左走一层就把当前节点压入调用栈直到走不动了才弹出、取值、再往右走。这个过程完全对应了中序遍历的定义左、根、右。但面试时如果只给出递归版本通常只能算及格。因为递归版本暴露不了你对栈这个数据结构是否真的掌握——而树的深度优先遍历本质上就是手动控制栈的过程。面试官经常追问如果树特别深递归会不会出问题能不能用非递归方式实现这个追问背后有个真实场景一棵极端不平衡的链状二叉树每个节点只有左孩子递归深度等于树的节点数。在LeetCode上往往没事但在真实工程环境里递归栈深度过大会导致StackOverflowError或者进程崩溃。所以掌握迭代写法不只是为了面经好看它本身就是一种工程上的备选方案。2.2 迭代版本理解先深入左子树再回头的核心节奏中序遍历的迭代写法需要自己维护一个栈。逻辑可以这样描述从根节点出发一直往左走把沿途的节点依次压入栈。当走到None时弹出栈顶节点记录它的值。然后转向该节点的右孩子重复刚才一路向左的过程。def inorder_traversal_iter(root): res [] stack [] cur root while cur or stack: # 一路向左把路径上的节点全部入栈 while cur: stack.append(cur) cur cur.left # 弹出栈顶访问它 cur stack.pop() res.append(cur.val) # 转向右子树 cur cur.right return res这个代码的节奏感非常重要。第一次写迭代中序时最常见的错误是先弹出再判断左子树导致节点访问顺序错乱忘记在弹出后把cur指向cur.right结果循环永远在左子树上徘徊内层while cur没有判空在None上访问.left直接报AttributeError。我自己当年的做法是拿一张小纸片画一棵只有三个节点的树根、左、右手动推演一遍压栈、弹栈的过程。推完之后再看代码思路一下子就通了。手动推演一个最小例子是排除这类逻辑错误最快的方法。2.3 颜色标记法背不下来时的万能逃生方案如果你面试时突然忘了迭代写法的细节有一个非常讨巧的方案——颜色标记法。这个方法其实是用标记来模拟递归栈的状态机每个栈元素是一个元组包含节点本身和一个布尔标记。第一次遇到节点时标记为False表示还没访问过把它和它的左右子节点按逆序压栈。第二次遇到节点时标记为True表示已经处理完左右子树这时直接取值。def inorder_traversal_marked(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: # 栈是后进先出所以先压右再压根最后压左 stack.append((node.right, False)) stack.append((node, True)) stack.append((node.left, False)) return res我个人觉得这个方法的最大价值不是性能而是不用费脑子记何时弹栈、何时转向。你只要记住中序的序列应该是什么顺序然后按这个顺序从右往左压栈就行。同理前序和后序也可以用同一套模板改一行顺序非常适合临场应变。2.4 Morris遍历O(1)空间的冷门考点Morris遍历是一股清流派它通过临时修改树的结构线索化把空间复杂度压到O(1)。核心思路是利用叶子节点的空指针指回中序的后继节点。下面给一个判空版本def inorder_traversal_morris(root): res [] cur root while cur: if not cur.left: # 没有左子树直接访问当前节点然后去右子树 res.append(cur.val) cur cur.right else: # 找到当前节点左子树里最右边的节点即中序前驱 prev cur.left while prev.right and prev.right ! cur: prev prev.right if not prev.right: # 第一次访问建立线索回到当前节点 prev.right cur cur cur.left else: # 第二次访问说明左侧都处理完了访问当前节点恢复树结构 prev.right None res.append(cur.val) cur cur.right return res这个算法的关键点在于那个第二次访问的判断当prev.right cur时说明当前节点的左子树已经完全处理完且线索已经被建立过这一步是在恢复原状。Morris遍历在面试中属于加分项通常只有大厂深挖算法细节时才会被问到。它需要你对中序遍历的前驱后继关系有非常清晰的理解写起来容易绕晕——我的建议是如果没有充足把握正式面试时还是优先用迭代版Morris主要用来体现广度。2.5 中序的三个访问版本复杂度对比版本时间复杂度空间复杂度实际应用递归O(n)O(h)最坏O(n)代码最简洁笔试优先迭代显式栈O(n)O(h)最坏O(n)避免栈溢出面试常考颜色标记法O(n)O(2n)思路统一临场不易写错MorrisO(n)O(1)空间极致理解门槛高n是节点数h是树高。从中序的性质来说它最大的价值体现在二叉搜索树上——对BST做中序遍历得到的结果一定是有序的。这个性质直接引出了一堆题目比如LeetCode 230BST第K小元素、538BST转累加树第一反应都可以是中序。3. 层序遍历BFS框架与必须避开的深坑3.1 标准BFS模板队列每层先取size层序遍历要求按层输出每一层的节点放进一个小列表所有层组成一个二维数组。标准写法是这样的def level_order(root): res [] if not root: return res from collections import deque q deque([root]) while q: level_size len(q) level [] for _ in range(level_size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return resBFS用队列保证先进先出根节点入队出队时把它的左右孩子依次入队。整个过程就像从根向下一层一层铺开。3.2 一个最容易踩的坑动态取len(q)导致分层错乱新手最常见的层序错误写法是在for循环里直接用for node in q或者在while q循环里不提前保存level_size直接循环len(q)次。这有什么问题看这段错误示例while q: level [] for _ in range(len(q)): # 注意range在进入循环前执行一次 node q.popleft() ...如果range在for循环开始时被执行一次那么len(q)是固定的其实没问题。真正的问题是另一种while q: level [] i 0 while i len(q): # len(q)每次都会重新计算会越来越小 node q.popleft() level.append(node.val) ... i 1在这个版本里len(q)随着popleft执行不断减少后面的判断条件就失去了固定本层节点数的意义。更隐蔽的写法是while q: level [] for node in q: # 遍历一个不断变化的deque行为不可控 ...这些都是我在真实环境和给别人review代码时见过的坑。安全做法就是进入每一层之前先把len(q)存下来然后用range在这个快照上循环。3.3 BFS的变体锯齿形、右视图、每层平均值层序遍历的模板一旦写好可以平趟一大半同类题目。103. 二叉树的锯齿形层序遍历——奇数层从左往右偶数层从右往左。最简单的做法是先按标准层序遍历拿到res然后对偶数下标的小列表反转一次res level_order(root) for i in range(1, len(res), 2): res[i].reverse() return res这个变体的重点是不要改变BFS本身的遍历顺序只调整最终输出代码最不容易出错。199. 二叉树的右视图——每层最右边的节点构成结果。直接在BFS循环里判断i level_size - 1时取值即可。637. 二叉树的层平均值——每层求和除以层大小。429. N叉树的层序遍历——把node.left / node.right改成遍历node.children这个列表。这些题的共同点是层这个维度在结果里必须可见所以BFSsize快照是最自然的解法。如果你发现一道树的题目要求结果的嵌套结构本身就按层分优先想BFS不要一上来就尝试DFS递归传depth参数。3.4 从工程视角看BFS的适用边界BFS的空间复杂度最坏是O(n)——当这棵树是满二叉树时最后一层大约有n/2个节点同时待在队列里。这个开销在真实环境里有时需要考虑。比如处理一颗几十万节点的XML树或文件目录树时BFS的内存峰值比DFS高不少但优点是它天然是就近访问对缓存友好也不会像DFS那样一口气扎到最深处。我在实际项目里用BFS处理过组织架构树、菜单树这类数据因为这类业务场景天然按层级展示。建议你学这道题时别只在OJ上跑通可以顺手想想如果让你把一棵目录树按层级输出成JSON数组你是不是也能复用这套模板能复用才说明真的会了。3.5 一个反向思路用DFS做层序遍历很多人不知道层序遍历也可以递归来做只不过要额外带一个depth参数def level_order_dfs(root): res [] def dfs(node, depth): if not node: return if depth len(res): res.append([]) res[depth].append(node.val) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return res这其实是在用DFS模拟BFS的输出。它比队列版本更简洁在某些变体题比如让你输出每层的最小值里也完全适用。我自己一般用它做笔试快速AC用队列版本做面试细节讲解——两者都要会因为面试官可能追问还有别的实现方式吗。4. 为什么你写的二叉树程序总是报运行时错误热搜里有一个非常经典的问题写二叉树程序时为什么总是报运行时错误。这个现象几乎每个刷题人都经历过。我复盘了自己和身边朋友踩过的坑把根因归为这几类。4.1 误区一没理解LeetCode的输入数组和TreeNode的关系很多新手看到题目输入是[1,2,3,null,null,4,5]就以为这是一棵已经存在的树。但实际上LeetCode界面只是用层序序列在描述这棵树运行代码时系统会把数组构造成一棵真正的二叉树传给你的函数。你拿到的root可能长这样1 / \ 2 3 / \ 4 5但如果你自己想在本地跑就必须手动构造。很多人直接在本地用[1,2,3,null,null,4,5]调用函数就会报错。正确做法是写一个数组转二叉树的辅助函数from collections import deque def build_tree(values): if not values or values[0] is None: return None root TreeNode(values[0]) q deque([root]) i 1 while i len(values): node q.popleft() if i len(values) and values[i] is not None: node.left TreeNode(values[i]) q.append(node.left) i 1 if i len(values) and values[i] is not None: node.right TreeNode(values[i]) q.append(node.right) i 1 return root这个辅助函数其实就是用队列模拟层序构造和层序遍历的BFS模板是一对镜像操作。如果你层序遍历学明白了这个构造代码花五分钟就能推出来。4.2 误区二忽略None判定导致的空指针访问二叉树跑的几乎都是递归或循环每一条分支都可能遇到None。很多人写while cur.left: cur cur.left但忘记在函数开头或关键位置判root是否为None。当输入是空树[]时直接访问root.left就会抛出AttributeError。LeetCode虽然给了Constraints比如节点数范围但很多题目并不保证树非空。安全习惯是所有二叉树递归函数第一行先做空判断所有循环内访问子节点前先确认当前节点存在。4.3 误区三递归没写终止条件或者终止条件错误写中序递归时最经典的错误是只写了向左递归和访问节点忘记向右递归def dfs(node): if not node: return dfs(node.left) res.append(node.val) # 缺了 dfs(node.right)导致只遍历左子树这个错误运行时不会报错但输出会漏掉一大半节点如果你只是对着题目死磕为什么结果长度不对不容易定位。排查方法很简单先对一个只有三个节点的最小树根、左、右手动推演一遍你的代码看看访问顺序是否符合预期。4.4 误区四层序的队列操作顺序搞反层序遍历报错多数发生在deque操作上。比如忘记import collections或者把popleft()写成了pop()——后者会从队尾弹出节点导致顺序完全错乱返回结果层级混乱但不报错。还有人在while q里递归调用BFS导致队列在遍历过程中又被追加节点死循环。这类错误的排查链路我建议这样走打印验证树结构先用层序方法遍历一遍整棵树输出所有节点的值确认传入的树和你以为的一样。手动走一个最小两层树比如[1,2,3,4,5,6,7]把每次入队、出队、取值的过程写出来和代码执行结果对照。检查边界条件空树、单节点、只有左子树或只有右子树分别跑一遍。把这三步做成排查习惯二叉树题目在运行时错误上浪费的时间会大幅减少。4.5 四种常见错误的对照表症状根因对策AttributeError: NoneType object has no attribute left没判空访问子节点所有递归和循环内先判断当前节点结果为空的列表层序构造辅助函数没建出新树用build_tree先验证root非空输出漏节点、顺序错乱栈或队列操作顺序错误手动推演最小树核对压入顺序程序死循环递归没有终止条件或队列内动态追加节点打印每步操作检查边界条件我自己debug这类问题的习惯是在关键循环里加临时的print看看每次操作的节点到底是什么。哪怕题目OJ不接受print输出本地调试时打印出来观察定位速度会快很多定位完再删掉print对最终提交没有影响。5. 从背代码到画递归树真正吃透这两道题的方法5.1 手动构建一棵小树画出它的调用过程吃透遍历题最笨也是最有效的方法是在纸上画一棵树用三种不同颜色标出前序、中序、后序的访问顺序。比如用一个简单测试用例说明1 / \ 2 3 / \ \ 4 5 6中序遍历的序列应该是4, 2, 5, 1, 3, 6。你在纸上画好之后对照迭代栈的压弹过程走一遍就能体会一路向左压栈弹出访问再转向右这句话的物理意义。二叉树遍历不是靠背序列是靠理解何时访问根节点——中序是左子树都压完入栈之后弹出栈顶也就是最左下的节点这个过程自然保证了先访问左子。5.2 时间复杂度与空间复杂度的严谨分析两道题的操作都遍历全部节点一次时间复杂度必然是O(n)。空间复杂度分开看中序递归版递归栈深度最大是树高h最坏情况链状树O(n)平均O(log n)。中序迭代版显式栈里最多存放一条左链上的节点同样是O(h)。Morris版O(1)额外空间但代价是修改树结构工程上必须保证不改变原树时慎用。层序BFS队列最多同时容纳一层的节点满二叉树最坏O(n/2)≈O(n)。面试时如果能把这个复杂度分析讲清楚比多刷十道题都管用。面试官接下来大概率会问如果内存有限你会用哪种遍历这时候Morris的意义就体现出来了。5.3 二分的后续题单从这两道题能直接延伸到哪LeetCode 98 验证二叉搜索树中序遍历得到序列后检查是否严格递增。LeetCode 230 二叉搜索树中第K小的元素中序计数数到第K个直接返回。LeetCode 103 锯齿形层序遍历BFS模板奇数层反转或双端队列头插。LeetCode 199 二叉树右视图BFS每层取最后一个。LeetCode 107 自底向上层序遍历先正着层序最后整体反转。LeetCode 236 最近公共祖先DFS后序或BFS找出两条路径再求交点。这些题的共同特点是把一道树题拆成遍历和业务逻辑两部分——遍历管顺序业务逻辑管判断。你把94和102练透后面这些题可以顺手解掉。5.4 面试答题时的最佳策略正式面试时碰到二叉树遍历题我建议按这个顺序组织你的回答第一版给递归实现3分钟内写完说明思路清晰形成baseline。追问或主动展示再给迭代实现说明你了解递归栈可能溢出的问题能手动控制栈。如果面试官继续深挖提Morris把空间复杂度从O(h)讲到O(1)阐释线索化思想。层序遍历题先讲BFS的队列模板再讲size快照的意义然后主动提出DFS深度参数也可以实现同样的输出结构。这套节奏的目的是展示你有多个层次的认知能快速解题能讲复杂度能聊边界问题能主动拓展变体。很多候选人只停在第一步就丢掉了展示的机会。5.5 把遍历模板沉淀成本能最后聊聊实际的练习方法。我的做法是同一道题至少写三遍。第一遍看着题解写理解每一行的作用第二遍合上书从零写逼自己回忆关键逻辑第三遍在纸上手写伪代码模拟面试环境。三道写完这个模板就烙进脑子了。把中序迭代和层序BFS这两个模板沉淀下来之后你会发现后面遇到的大部分树题第一步都是先想清楚它需要哪种遍历第二步才是补业务逻辑。这也是为什么很多人刷题刷到后期会回头总结这些模板——它们才是整个二叉树题型的骨架。最后再分享一个我自己的小习惯。每次写完二叉树题我会故意试几个极端用例空树、只有左子树的链状树深度很大的那种、完全二叉树、只有右子树的退化树。这几个用例不仅能验证代码的健壮性还能让你真正确认自己理解了遍历过程的每一步。当年我做完这两道题后把目标从通过改成了任何一棵树都能准确画出它的遍历过程中栈或队列的状态变化从这之后二叉树类型的题我基本没再慌过。

二叉树遍历全解析：中序与层序，从DFS到BFS的代码模板

相关推荐

ESP32-C3电容触摸闹钟设计：从物理交互到行为反馈

Android线程安全与锁机制：从崩溃排查到实战选型

FPGA数据流设计：FIFO与AXI-Stream握手协议的工程实践

更多资讯

Python手写进度条：print隐藏参数与回车符实现终端实时刷新

STM32驱动DS1302实时时钟：从接线到校准的完整实践

2026论文降重工具哪家好用？沁言学术与QuillBot等AI写作工具对比

基础DP模型详解：状态定义、转移方程与背包、区间、树形DP实战

Matlab传染病模型实战：从SEIR方程到参数拟合与干预推演

商贸企业采购退货财务处理与管家婆系统操作指南

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？