企业官网建设流程全解析

二叉树的三种遍历方式，你掌握了几种？

我当年学数据结构的时候，第一次被二叉树弄得有点懵，倒不是因为树这个结构本身有多难理解，而是动不动就“递归递归”，课上听得明明白白，下来自己一写代码就原地宕机。后来刷题、做项目、给新人讲这块内容，来来回回折腾了很多次，才算把先序、中序、后序这三种遍历方式真正吃透。这篇文章我就把这三种遍历方式从头到尾拆一遍，不光告诉你“怎么遍历”，更重要的是告诉你“为什么要这样遍历”，递归怎么写、非递归怎么写、面试怎么考，一次说清楚。

这篇文章适合谁看？正在学数据结构的学生、准备算法面试的求职者，以及工作中偶尔要用到树结构但总得现查资料的朋友。看完之后，你能很清晰地写出三种遍历的递归版本和非递归版本，能理解它们各自的应用场景，还能解决一个面试中特别高频的题型——根据先序和中序还原二叉树。

1. 内容整体设计与思路拆解

1.1 为什么遍历方式对二叉树这么重要

二叉树这种数据结构和数组、链表最大的区别在于：数组是线性的，从头到尾花一趟就遍历完了。链表虽然指针跳来跳去，但每条路径也是单向的。二叉树就不一样了——它的每一个节点都有两个孩子，你在根节点的时候要决定“先往哪边去”，到了子树又要再做决定。这个“决定顺序”就是遍历方式。

用生活里的例子来想：你到一个岔路口，左边是一座美术馆，右边是一座科技馆，美术馆里面又分两个展厅，科技馆里面也分两个展厅。如果你是“深度优先”的逛法，你会选择先逛完美术馆的所有展厅，再逛科技馆。这个“先逛完左边再逛右边”的思路，对应的就是二叉树里的“深度优先遍历”。而三种遍历方式的区别，其实就是“什么时候去逛这个节点自己”——是在逛子节点之前、之中，还是之后。

这就有意思了：遍历顺序直接决定了你得到的结果序列。先序遍历的结果，根节点永远在最前面；中序遍历的结果，左子树的节点永远在根节点的左边；后序遍历的结果，根节点永远在最后面。这些特性不是巧合，它们背后是有严格的逻辑支撑的，理解了这个逻辑，很多题目不用死记硬背就能推出来。

1.2 三种遍历方式的核心区别

我用一句话来总结三种遍历方式的定义，这句话我每次教人的时候都会说：

• 先序遍历：先访问根节点，再遍历左子树，最后遍历右子树。
• 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
• 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

注意这三个定义里的关键词不同：先序是“根左右”，中序是“左根右”，后序是“左右根”。就这么个顺序差别，造就了三种截然不同的结果序列。

我用一棵小树来做个演示。假设有一个二叉树，它的结构是这样的：根节点是A，A的左孩子是B，A的右孩子是C，B的左孩子是D，B的右孩子是E，C的左孩子是F。这棵树怎么表示呢？在代码里通常是这样：

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

然后构建这棵树：

root = TreeNode('A') root.left = TreeNode('B') root.right = TreeNode('C') root.left.left = TreeNode('D') root.left.right = TreeNode('E') root.right.left = TreeNode('F')

这棵树画出来就是：A在最上面，B和C在第二层，D、E、F在第三层。好，现在我们来推一下三种遍历的结果：

• 先序遍历：A B D E C F。根节点A在最前面，然后走左子树B，B的左孩子D，B的右孩子E，再回来走右子树C，C的左孩子F。
• 中序遍历：D B E A F C。先走A的左子树，左子树里又要先走B的左子树D，然后访问B，再访问B的右子树E，回到A，访问A，再走右子树C的左子树F，最后访问C。
• 后序遍历：D E B F C A。先走左子树，左子树里先走B的左子树D，再走B的右子树E，然后访问B，再走右子树C的左子树F，访问C，最后访问根A。

你细看这三个结果，会发现一个规律：先序遍历里A是第一个，后序遍历里A是最后一个，中序遍历里A在中间位置。这个规律是后面做“根据两种遍历还原二叉树”这类题目的基础。

2. 核心细节解析与实操要点

2.1 递归遍历的代码实现与调用过程拆解

递归是二叉树遍历里最常见的实现方式，因为树的定义本身就带有递归性质——一棵树的左子树和右子树，本身也是树。你天然可以用同样的函数去处理它们。

先来看看先序遍历的递归代码实现，我用的是Python，C++和Java基本也是同样的思路：

def preorder_traversal(root): if root is None: return [] result = [] result.append(root.val) result += preorder_traversal(root.left) result += preorder_traversal(root.right) return result

这个代码逻辑很清晰：根节点不为空，就把根节点的值放入结果列表，然后递归处理左子树，再递归处理右子树。

再看中序遍历：

def inorder_traversal(root): if root is None: return [] result = [] result += inorder_traversal(root.left) result.append(root.val) result += inorder_traversal(root.right) return result

区别就是把“访问根节点”的操作放在了“递归左子树”和“递归右子树”之间。

最后是后序遍历：

def postorder_traversal(root): if root is None: return [] result = [] result += postorder_traversal(root.left) result += postorder_traversal(root.right) result.append(root.val) return result

你对比一下这三段代码，其实差别只有一行——result.append(root.val)这个操作的位置。放在递归左子树之前就是先序，放在递归左子树和递归右子树之间就是中序，放在两个递归之后就是后序。

这里我要多讲一句：递归的“隐式栈”这个概念很重要。很多初学者能写出递归代码，但不太清楚背后发生了什么。每次递归调用，系统都会把当前函数的局部变量、参数和返回地址压入一个系统栈，等到递归返回时再弹出来继续执行。所以递归遍历的顺序，本质上是这个系统栈的压栈和弹栈顺序决定的。

用刚才那棵树来跟踪一下先序遍历的过程：访问A，打印A，然后递归左子树。在递归左子树时，A这个函数的状态被系统栈记住了（当然在这里其实A后面还有右子树要处理）。进入B节点，打印B，递归B的左子树，打印D，D的左右子树都为空，返回到B，然后递归B的右子树，打印E，再返回B，B的函数执行完毕，回到A，递归A的右子树，打印C，再递归C的左子树，打印F，完事。

这个过程理解了，你就能明白另一个问题：为什么递归代码看着简单，但真正理解它根本不用背——你推一遍这个过程，自然就记住了。

2.2 非递归遍历的代码实现与手动栈思路

面试官经常会让写非递归版本的遍历，尤其是中序和后序。这个考的不是“会不会用栈”，而是你究竟理解不理解递归的过程。

先序遍历的非递归实现相对简单，因为根节点优先访问，所以你在压栈的时候，先弹出根节点，然后压入右孩子，再压入左孩子——注意顺序，右先左后，这样栈顶弹出来的就是左孩子，符合“先左后右”的遍历顺序。

def preorder_traversal_iterative(root): if root is None: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result

中序遍历的非递归实现就要稍微转个弯了。核心思路是：从根节点出发，一路沿着左孩子往下走，把沿途经过的节点全部压入栈中，直到左孩子为空。这时弹出栈顶元素——它就是当前子树里最左边的节点——访问它，然后走到它的右孩子，重复这个过程。

def inorder_traversal_iterative(root): result = [] stack = [] current = root while current or stack: while current: stack.append(current) current = current.left current = stack.pop() result.append(current.val) current = current.right return result

后序遍历的非递归实现是最烦人的，它有几种写法。一种比较取巧的思路是：后序遍历是“左右根”，如果反过来看就是“根右左”——这其实很像先序遍历，只要把“先序”里的左右压栈顺序反过来，得到的就是“根右左”，然后把这个结果反转，就得到“左右根”，也就是后序遍历的结果。

def postorder_traversal_iterative(root): if root is None: return [] result = [] stack = [root] while stack: node = stack.pop() result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) result.reverse() return result

这个写法我非常推荐，因为好记、不容易错，而且面试的时候面试官能一眼看懂你的思路。

这里我说一个实际开发里踩过的坑：递归做多了会导致堆栈溢出。Python默认的递归深度是1000层左右，如果二叉树退化成了一条链，深度可能达到上万甚至好几万，递归版本就会直接报RecursionError或者栈溢出。所以生产环境里如果需要遍历深度很大的树，最好用非递归版本。这一点我在做编译原理相关的AST（抽象语法树）处理时就遇到过，遍历一棵深度很大的语法树，用递归版本在特定输入下会崩，改成非递归之后问题就消失了。

2.3 时间复杂度与空间复杂度分析

三种遍历方式的时间复杂度都是O(n)，因为每个节点都被访问且仅被访问了一次。这一点不管递归还是非递归都一样。

空间复杂度就有区分了。递归版本是O(h)，h是树的高度——因为递归的过程中，系统栈最多压入h层函数调用。非递归版本的先序和中序是O(h)，需要开一个栈来存放节点。而后序遍历的非递归版本，如果像我上面那样用逆向思路，额外空间同样是O(h)，最后反转结果数组的那个O(n)是返回值本身占用的空间，不算额外空间。

但是，最坏情况下树会退化成链表，这时候树的高度等于节点数n，空间复杂度就变成O(n)了。这个“退化”场景在面试里也是高频考点：一个只有左孩子的二叉树，它的先序遍历结果就等同于这个链表从头到尾的遍历结果。

我之前带过一个同学，他说“二叉树遍历不是很简单吗，就O(n)呗”——这个回答其实犯了个典型错误：把时间复杂度和空间复杂度混为一谈了。时间和空间是两个维度，都要考虑。

3. 实操过程与核心环节实现

3.1 根据先序遍历和中序遍历还原二叉树

这个题型是面试里的高频题，也是很多数据结构的课后作业题。热词里也出现了“知道二叉树先序和中序 确定树的样子”，说明很多人都在为这个题头疼。

核心思想其实很简单，关键就一句话：先序遍历的第一个节点一定是树的根节点，找到这个根节点在中序遍历中的位置，左边就是根节点的左子树，右边就是根节点的右子树。然后对左子树和右子树再做同样的操作，递归下去，就能还原整棵树。

我用一个例子来走一遍完整流程。假设先序遍历结果是：[3, 9, 20, 15, 7]，中序遍历结果是：[9, 3, 15, 20, 7]。

第一步，先序遍历的第一个元素是3，所以根节点的值是3。在中序遍历里找到3，它把数组分成了两部分：左边是[9]，右边是[15, 20, 7]。所以3的左子树就是由[9]构成的树，右子树是由[15, 20, 7]构成的树。

第二步，处理左子树。先序里紧跟着的两个元素分别是9和20，但根据中序划分，9属于左子树，20属于右子树。于是只用先序里的[9]和中序里的[9]来构建左子树——9这个节点没有左孩子，也没有右孩子。

第三步，处理右子树。右子树在先序里的对应元素是[20, 15, 7]（因为20是左子树之后的第一个节点，说明右子树的根就是20）。中序里右子树部分是[15, 20, 7]，找到20，左边[15]就是它的左子树，右边[7]就是它的右子树。所以20的左孩子是15，右孩子是7。

最终的树是这样的：3是根，9是左孩子，20是右孩子，15是20的左孩子，7是20的右孩子。你用中序遍历验证一下：9, 3, 15, 20, 7，完全正确。

代码实现如下：

def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder[0] root = TreeNode(root_val) mid_index = inorder.index(root_val) left_inorder = inorder[:mid_index] right_inorder = inorder[mid_index + 1:] left_preorder = preorder[1:1 + len(left_inorder)] right_preorder = preorder[1 + len(left_inorder):] root.left = build_tree(left_preorder, left_inorder) root.right = build_tree(right_preorder, right_inorder) return root

这段代码里有个非常关键的细节：根据左子树节点的数量，去先序数组里切出对应的部分。左子树的中序长度是mid_index，所以左子树的先序部分就是从preorder[1]开始，往后数mid_index个元素。剩下的就是右子树的先序部分。

这个逻辑想明白了，整道题就通了。而如果只知道后序和中序，也可以做同样的事——只不过这时候根节点在后序数组的最后一个，其他思路完全一样。

3.2 三种遍历方式的实际应用场景

为什么要区分这三种遍历？因为它们在不同的场景下各有用途。我不建议“死记三种遍历的定义然后背代码”，更好的方式是理解它们各自解决了什么问题。

先序遍历最常见的应用是做树的深拷贝——你要复制一棵树，必须先复制根节点，再复制左子树和右子树，这个顺序天然就是先序遍历。另一个典型场景是序列化：把二叉树存到文件里或者传到网络上，先序遍历是最自然的序列化顺序，因为你知道第一个元素一定是根节点。

中序遍历在二叉搜索树（BST）里有一个极其重要的特性：对一棵二叉搜索树做中序遍历，得到的结果是升序排列的。这个特性在很多算法题里都会用到。比如判断一棵树是不是二叉搜索树，最常用的方法之一就是中序遍历它，看结果是不是严格递增的。再比如求二叉搜索树的第k小节点，也可以通过中序遍历一次搞定。

后序遍历的典型应用场景是树的释放、删除操作——你要删除一棵树，必须先删除它的孩子节点，才能删除当前节点，否则会出现访问已释放内存的问题。另一个场景是表达式树的计算：一棵表达式树的根节点是运算符，左右子树是操作数，要计算这个表达式的值，必须先把左子树的值和右子树的值分别算出来，然后才能执行根节点的运算，这个顺序恰好就是后序遍历的顺序——中序遍历表达式树得到的是中缀表达式，后序遍历得到的是后缀表达式。

我在实际做编译原理相关的项目时，处理AST的时候经常使用后序遍历：先递归处理子节点，再处理当前节点。比如做语法树的分析，你要先分析子表达式的类型，才能推断出当前表达式的类型，这种模式跟后序遍历是一模一样的结构。

3.3 层序遍历：另一种必须掌握的遍历方式

虽然题目说的是“三种遍历方式”，但在面试里“层序遍历”同样是被高频考察的，尤其是“按层输出二叉树节点”这种题。甚至很多教科书里会把层序遍历也算作二叉树的“第四种”遍历方式，所以我还是花点篇幅讲一下。

层序遍历的思路是：从根节点开始，先访问根节点，再访问它的左孩子和右孩子，然后访问左孩子的孩子、右孩子的孩子，一层一层往下走。它对应的是“广度优先”的搜索顺序。

层序遍历的实现离不开队列这个数据结构：

from collections import deque def level_order_traversal(root): if root is None: return [] result = [] queue = deque([root]) while queue: node = queue.popleft() result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result

关键点在于：队列的先进先出特性，保证了每一层的节点会按照从左到右的顺序被处理。每个节点出队时，它的孩子节点会被放到队尾，这样就能保证“先处理完一整层，再进入下一层”。

层序遍历的应用也很广泛。求二叉树的最大宽度，就是层序遍历时统计每一层的节点数；判断一颗二叉树是不是完全二叉树，也可以用层序遍历来判断；还有“二叉树的最小深度”问题，用层序遍历可以在找到第一个叶子节点时立即结束，效率比深度优先更优。

面试里层序遍历还有个经典变体：“按层输出”，即每一层的节点单独放进一个列表里。这个需要你在循环里记录当前层的节点数，然后一次性处理完这一层的所有节点：

def level_order_layers(root): if root is None: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result

注意这里有个坑：level_size必须在处理当前层之前取出来。如果你在循环里动态用len(queue)判断，就会出问题，因为队列的长度随着节点的入队出队在不断变化，你没法用它来控制“只处理当前层”的节点数。这个问题我见过很多新手踩进去过。

4. 常见问题与排查技巧实录

4.1 递归遍历时常见的错误与解决

错误一：递归终止条件写错。很多初学者写的终止条件是if root == None: return []，这个没问题。但有的人会写成if root is None: return None，然后在上一层代码里对None做拼接操作，直接报TypeError。我的建议是：明确你的函数返回值是什么，如果约定返回的都是列表，那么空树也要返回[]，这样上层就不用做额外判断。

错误二：把“访问根节点”放错了位置。先序、中序、后序的本质区别就是这一行代码的位置。你写代码的时候，先把三种遍历的代码模板放在一起对比，确认自己写的到底是哪一种——是根左右、左根右还是左右根。这个必须在动手前想清楚，不要边写边想。

错误三：递归深度超限。前面提到过，Python默认递归深度是1000层左右。如果二叉树深度比较大，或者测试用例里有一条很长的链，递归版本就会报RecursionError: maximum recursion depth exceeded。解决办法有两个：一个是用sys.setrecursionlimit()调大递归深度限制，另一个是改用非递归版本的栈实现。我建议优先用非递归版本，因为调大递归限制只是治标不治本，深度特别大的时候依然可能崩溃。

4.2 非递归遍历时容易搞混的逻辑

非递归先序遍历里有个细节：压栈顺序是“先右后左”。为什么要这样？因为栈是先进后出的，你想先访问左孩子，就必须让左孩子后进栈，这样它才能在栈顶被先弹出。如果把左右顺序搞反了，得到的先序顺序就反过来了。

非递归中序遍历里最容易错的地方是：外层循环的终止条件。要保证“当前节点不为空或者栈不为空”才能继续循环，少了任何一半都会出问题。如果少了“当前节点不为空”，当栈弹空但当前节点还有右子树时，循环就提前结束了；如果少了“栈不为空”，当当前节点为空但栈里还有节点时，循环也会提前结束。

非递归后序遍历用“反向先序+反转”这个技巧时，要注意压栈顺序也要反过来——先压左孩子再压右孩子，这样得到的结果才是“根右左”，反转之后才是“左右根”。

为了让你方便对照记忆，我把这些问题整理成了表格：

4.3 根据遍历序列还原二叉树时的易错点

根据先序+中序还原二叉树时，最常见的错误是切分先序数组时没有依据“左子树节点数”来切分，而是想当然地从中序根节点位置来切。这里一定要记住：先序和中序的切分方式不同——中序用根节点位置切分，先序用“左子树节点数”来切分。

我再举一个易错的例子：如果树的节点值有重复，那么inorder.index(root_val)会找到第一个匹配的位置。如果二叉树里存在相同值的节点，这种“根据值确定根节点位置”的方法就不靠谱了。所以数据结构里默认树节点的值不重复，或者至少要能通过某种方式唯一确定节点的身份。如果真遇到重复值的场景，你需要给每个节点附加唯一标识（比如在序列化时带上索引或地址信息），否则两种遍历序列无法唯一还原一棵二叉树。

另外，只知道先序和后序是没法唯一还原二叉树的，除非这棵树是“满二叉树”或者“真二叉树”（每个节点要么没有孩子，要么有两个孩子）。因为先序和后序只能确定根节点——先序第一个、后序最后一个——但无法区分哪些节点属于左子树、哪些属于右子树。这个知识点有时候会出现在面试的“陷阱题”里，大家要留个心眼。

4.4 调试二叉树遍历的实用技巧

我调试二叉树遍历代码时，最常用的手段就是“可视化输出”。对于递归版遍历，你可以在每次访问节点的位置打印输出，加上缩进表示递归深度，这样能很直观地看出递归的执行过程。

一个简单但有效的方法是把二叉树的结构直接打印成“带缩进的文本”：

def print_tree(root, level=0, label='root'): if root is None: return print(' ' * level + f'{label}: {root.val}') print_tree(root.left, level + 1, 'L') print_tree(root.right, level + 1, 'R')

这样你在测试时，先打印树的结构，确认树本身是对的，再去验证遍历结果，就很容易定位问题出在“建树阶段”还是“遍历阶段”。

另外一个技巧是：把三种遍历的结果同时打印出来，手动演算一遍，看结果是相符。比如我在测试还原二叉树的代码时，会这样操作：先随机生成一棵树，然后分别得到它的先序、中序序列，再用“先序+中序”还原出一棵新树，最后对这两棵树分别做层序遍历，逐层比较是否一致。如果发现不一致，说明还原逻辑有问题。

我实际写算法题的时候，还有一种很好用的做法：写一个“暴力对照版”——用一个思路简单但效率不高的实现，跟优化版本在多组测试数据上做对照，确保输出一致。比如递归遍历实现很好写，我就用递归版作为基准，测试非递归版本是否跟它一致。这个习惯帮我省了很多排查问题的时间。

5. 写在最后的经验

二叉树遍历这个知识点，说难也难，说简单也简单。难的地方在于递归理解和栈的应用，简单的地方在于——它本质上就是一个顺序问题：你先处理什么、后处理什么，就是这个顺序决定了遍历类型。

我个人在实际操作中的一个体会是：不要死背代码模板。把三种遍历方式的核心逻辑——“根节点访问时机不同”——理解透，然后把递归版本的代码推演一遍，再手动跟踪一棵具体树上递归的过程，是学这块内容最快的方式。等递归版本彻底理解了，非递归版本再去理解“用什么数据结构模拟递归”就行。

如果面试的时候被问到这块，可以多准备一个加分项：指出每种遍历在实际系统里的应用场景。面试官听了会认为你不是在“背知识点”，而是真正理解了这个数据结构的价值。

最后再分享一个小技巧，是我刷题和带人时经常用的一句话：看到二叉树相关的题，先问自己三个问题——它的根节点什么时候被处理？左子树和右子树谁先被处理？需不需要在子树处理完之前知道父节点？这三个问题想清楚了，不管题目怎么变，你的思路都不会走偏。