二叉树的三种遍历方式你掌握了几种我当年学数据结构的时候第一次被二叉树弄得有点懵倒不是因为树这个结构本身有多难理解而是动不动就“递归递归”课上听得明明白白下来自己一写代码就原地宕机。后来刷题、做项目、给新人讲这块内容来来回回折腾了很多次才算把先序、中序、后序这三种遍历方式真正吃透。这篇文章我就把这三种遍历方式从头到尾拆一遍不光告诉你“怎么遍历”更重要的是告诉你“为什么要这样遍历”递归怎么写、非递归怎么写、面试怎么考一次说清楚。这篇文章适合谁看正在学数据结构的学生、准备算法面试的求职者以及工作中偶尔要用到树结构但总得现查资料的朋友。看完之后你能很清晰地写出三种遍历的递归版本和非递归版本能理解它们各自的应用场景还能解决一个面试中特别高频的题型——根据先序和中序还原二叉树。1. 内容整体设计与思路拆解1.1 为什么遍历方式对二叉树这么重要二叉树这种数据结构和数组、链表最大的区别在于数组是线性的从头到尾花一趟就遍历完了。链表虽然指针跳来跳去但每条路径也是单向的。二叉树就不一样了——它的每一个节点都有两个孩子你在根节点的时候要决定“先往哪边去”到了子树又要再做决定。这个“决定顺序”就是遍历方式。用生活里的例子来想你到一个岔路口左边是一座美术馆右边是一座科技馆美术馆里面又分两个展厅科技馆里面也分两个展厅。如果你是“深度优先”的逛法你会选择先逛完美术馆的所有展厅再逛科技馆。这个“先逛完左边再逛右边”的思路对应的就是二叉树里的“深度优先遍历”。而三种遍历方式的区别其实就是“什么时候去逛这个节点自己”——是在逛子节点之前、之中还是之后。这就有意思了遍历顺序直接决定了你得到的结果序列。先序遍历的结果根节点永远在最前面中序遍历的结果左子树的节点永远在根节点的左边后序遍历的结果根节点永远在最后面。这些特性不是巧合它们背后是有严格的逻辑支撑的理解了这个逻辑很多题目不用死记硬背就能推出来。1.2 三种遍历方式的核心区别我用一句话来总结三种遍历方式的定义这句话我每次教人的时候都会说先序遍历先访问根节点再遍历左子树最后遍历右子树。中序遍历先遍历左子树再访问根节点最后遍历右子树。后序遍历先遍历左子树再遍历右子树最后访问根节点。注意这三个定义里的关键词不同先序是“根左右”中序是“左根右”后序是“左右根”。就这么个顺序差别造就了三种截然不同的结果序列。我用一棵小树来做个演示。假设有一个二叉树它的结构是这样的根节点是AA的左孩子是BA的右孩子是CB的左孩子是DB的右孩子是EC的左孩子是F。这棵树怎么表示呢在代码里通常是这样class TreeNode: def __init__(self, val0, leftNone, rightNone): 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在最前面然后走左子树BB的左孩子DB的右孩子E再回来走右子树CC的左孩子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 递归遍历的代码实现与调用过程拆解递归是二叉树遍历里最常见的实现方式因为树的定义本身就带有递归性质——一棵树的左子树和右子树本身也是树。你天然可以用同样的函数去处理它们。先来看看先序遍历的递归代码实现我用的是PythonC和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的左子树打印DD的左右子树都为空返回到B然后递归B的右子树打印E再返回BB的函数执行完毕回到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 非递归遍历时容易搞混的逻辑非递归先序遍历里有个细节压栈顺序是“先右后左”。为什么要这样因为栈是先进后出的你想先访问左孩子就必须让左孩子后进栈这样它才能在栈顶被先弹出。如果把左右顺序搞反了得到的先序顺序就反过来了。非递归中序遍历里最容易错的地方是外层循环的终止条件。要保证“当前节点不为空或者栈不为空”才能继续循环少了任何一半都会出问题。如果少了“当前节点不为空”当栈弹空但当前节点还有右子树时循环就提前结束了如果少了“栈不为空”当当前节点为空但栈里还有节点时循环也会提前结束。非递归后序遍历用“反向先序反转”这个技巧时要注意压栈顺序也要反过来——先压左孩子再压右孩子这样得到的结果才是“根右左”反转之后才是“左右根”。为了让你方便对照记忆我把这些问题整理成了表格遍历方式常用数据结构核心注意点典型错误先序遍历栈压栈先右后左压栈顺序搞反中序遍历栈先一路左走到底再弹栈向右循环终止条件少写当前节点判断后序遍历栈可用反向先序反转结果压栈顺序没跟着反过来层序遍历队列处理每层前先记录当前层节点数动态用len(queue)导致层边界错乱4.3 根据遍历序列还原二叉树时的易错点根据先序中序还原二叉树时最常见的错误是切分先序数组时没有依据“左子树节点数”来切分而是想当然地从中序根节点位置来切。这里一定要记住先序和中序的切分方式不同——中序用根节点位置切分先序用“左子树节点数”来切分。我再举一个易错的例子如果树的节点值有重复那么inorder.index(root_val)会找到第一个匹配的位置。如果二叉树里存在相同值的节点这种“根据值确定根节点位置”的方法就不靠谱了。所以数据结构里默认树节点的值不重复或者至少要能通过某种方式唯一确定节点的身份。如果真遇到重复值的场景你需要给每个节点附加唯一标识比如在序列化时带上索引或地址信息否则两种遍历序列无法唯一还原一棵二叉树。另外只知道先序和后序是没法唯一还原二叉树的除非这棵树是“满二叉树”或者“真二叉树”每个节点要么没有孩子要么有两个孩子。因为先序和后序只能确定根节点——先序第一个、后序最后一个——但无法区分哪些节点属于左子树、哪些属于右子树。这个知识点有时候会出现在面试的“陷阱题”里大家要留个心眼。4.4 调试二叉树遍历的实用技巧我调试二叉树遍历代码时最常用的手段就是“可视化输出”。对于递归版遍历你可以在每次访问节点的位置打印输出加上缩进表示递归深度这样能很直观地看出递归的执行过程。一个简单但有效的方法是把二叉树的结构直接打印成“带缩进的文本”def print_tree(root, level0, labelroot): 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. 写在最后的经验二叉树遍历这个知识点说难也难说简单也简单。难的地方在于递归理解和栈的应用简单的地方在于——它本质上就是一个顺序问题你先处理什么、后处理什么就是这个顺序决定了遍历类型。我个人在实际操作中的一个体会是不要死背代码模板。把三种遍历方式的核心逻辑——“根节点访问时机不同”——理解透然后把递归版本的代码推演一遍再手动跟踪一棵具体树上递归的过程是学这块内容最快的方式。等递归版本彻底理解了非递归版本再去理解“用什么数据结构模拟递归”就行。如果面试的时候被问到这块可以多准备一个加分项指出每种遍历在实际系统里的应用场景。面试官听了会认为你不是在“背知识点”而是真正理解了这个数据结构的价值。最后再分享一个小技巧是我刷题和带人时经常用的一句话看到二叉树相关的题先问自己三个问题——它的根节点什么时候被处理左子树和右子树谁先被处理需不需要在子树处理完之前知道父节点这三个问题想清楚了不管题目怎么变你的思路都不会走偏。