1. 先搞清楚遍历到底在做什么1.1 从一根链子讲起如果问你一个单链表怎么遍历你肯定张口就来从头节点开始顺着 next 指针一路走到底就完事了。为什么这么简单因为链表是一条线每个节点只有一个后继顺序是天然的不需要做选择。二叉树就不一样了。每个节点最多有两个孩子左子树和右子树。走到一个节点后你是先往左钻还是先往右钻还是先把当前节点记下来这就会产生不同的访问顺序。所谓前序遍历、中序遍历、后序遍历本质上就是“处理当前节点”这个动作发生在“访问左子树”和“访问右子树”之间的哪个位置。放在递归框架里更清楚任何一个二叉树遍历递归函数都只有三件事要做处理当前节点比如打印它的值或者累计求和递归访问左子树递归访问右子树而“处理当前节点”可以在第1步、第2步、第3步对应三种遍历。前序遍历就是先处理当前节点再访问左子树最后访问右子树中序遍历是先访问左子树再处理当前节点最后访问右子树后序遍历是先访问左子树再访问右子树最后处理当前节点。所以三种遍历的差别不是“一个不同的算法”只是处理时机不同。这是理解整篇文章最关键的一步。1.2 命名逻辑根节点站在队伍第几位很多初学者记不住三种遍历的顺序看到名字就懵。其实中文译名非常直观前序遍历根节点第一个被访问所以也叫“先根遍历”。中序遍历根节点在中间被访问左子树在前右子树在后所以叫“中根遍历”。后序遍历根节点最后一个被访问所以叫“后根遍历”。这里的“前中后”描述的是根节点在访问序列里的位置而不是整棵树从左到右的位置。一棵只有三个节点的完全二叉树根节点A左孩子B右孩子C四种访问顺序分别是前序A B C中序B A C后序B C A看根节点A分别出现在第一位、第二位、第三位名字就是这么来的。不过要注意在遍历普通二叉树的时候“左子树”和“右子树”各自内部也遵循同样的规则。前序不是简单地把所有左子树节点排完再排右子树而是每到一个子树都先处理根再递归处理左子树再递归处理右子树。很多人写代码时在这里逻辑绕晕后面我会用递归展开过程把这一点彻底讲透。1.3 被访问三次的节点你会在哪一次动手有一种特别形象的比喻递归遍历二叉树时每个节点实际上会被“路过”三次。第一次是从父节点下来刚进入这个节点第二次是左子树遍历完回到这个节点第三次是右子树遍历完也回到这个节点。这个说法放在递归里非常真实。你可以在代码里加一个打印语句验证一下每次进入函数时打印“进入”每次从左子树返回时打印“左回”每次从右子树返回时打印“右回”。跑一个小样例你会发现每个节点确实会被经过三次。那前序遍历就是在第一次路过时处理节点中序遍历就是在第二次路过时处理节点后序遍历就是在第三次路过时处理节点。这个视角对理解迭代写法特别有帮助因为迭代写法本质上就是用栈手动模拟这个“三次路过”的过程。特别是双色标记法会在节点第一次出栈时重新压回去标记为“已访问过左子树”第二次出栈时才真正处理这就把这个三次路过变成了显式状态。2. 递归实现三行核心逻辑走天下2.1 递归三要素先背下一套模板写递归遍历不需要每棵树都从头想一遍。“递归三要素”是所有递归问题的通用套路放到二叉树遍历上就是第一明确函数的功能。比如一个函数traverse(node)功能就是按顺序访问以 node 为根的整棵子树。第二找到递归出口。二叉树遍历的递归出口就是空节点判断当节点为 null 时直接返回不需要做任何处理。第三找出等价关系式。也就是把大问题拆成小问题访问一棵树等价于“处理当前节点 访问左子树 访问右子树”只是处理的时机不同。基于这三要素三种遍历的代码几乎只有一行之差# 前序遍历 def preorder(node): if not node: return visit(node) # 处理当前节点 preorder(node.left) # 访问左子树 preorder(node.right) # 访问右子树 # 中序遍历 def inorder(node): if not node: return inorder(node.left) # 先访问左子树 visit(node) # 再处理当前节点 inorder(node.right) # 最后访问右子树 # 后序遍历 def postorder(node): if not node: return postorder(node.left) # 先访问左子树 postorder(node.right) # 再访问右子树 visit(node) # 最后处理当前节点这个模板可以直接嵌套到很多具体题目里。所谓visit(node)不一定就是打印你可以换成收集到列表里、累加求和、判断某个条件等等。比如求二叉树节点个数就把 visit 改成count 1求最大值就把 visit 改成比较更新最大值。2.2 用一棵小树拆解前序递归过程光看代码还是有点抽象我建议你找个小例子手动走一遍。用下面这棵小树A / \ B C / \ \ D E F前序遍历的期望结果是A B D E C F。为什么 D 会排在 E 前面因为前序规则是先处理根再完整地访问左子树。B 的左子树里D 是左孩子E 是右孩子所以进入以 B 为根的子树后先处理 B再进入 B 的左子树处理 D然后回到 B 的右子树处理 E处理完整个 B 子树后才轮到 C。递归函数实际的执行轨迹是这样preorder(A)处理 A输出 A。调用preorder(B)进入左子树。处理 B输出 B。调用preorder(D)处理 D输出 D。D 的左右孩子都为空返回。回到 B调用preorder(E)处理 E输出 E。返回。回到 A调用preorder(C)处理 C输出 C。调用preorder(F)处理 F输出 F。输出序列是 A B D E C F完全符合“根左右”的顺序。这块有个新手特别容易犯的错以为前序遍历就是“从根开始一层一层往左然后一层一层往右”其实不是。前序是“每到一个子树先处理子树的根再处理子树的左链上的根然后回溯处理之前的右子树”。所以 D 和 E 是兄弟一定是一个完整的左子树处理完才轮到右边。2.3 中序和后序的递归轨迹差异中序遍历在同样的树上期望结果是D B E A C F。执行轨迹大概是进入 A不处理先去 A 的左子树 B进入 B不处理先去 B 的左子树 D进入 D左空、处理 D、右空返回到 B处理 B再进 B 的右子树 E处理 E返回到 A处理 A进 CC 有左子树吗没有所以处理 C再进 F处理 F。注意看中序遍历的结果里A 左边的节点全部来自 A 的左子树A 右边的节点全部来自 A 的右子树。这正是中序最重要的性质它能区分根节点的左右子树部分。后序遍历期望结果是D E B F C A。它的执行轨迹里根节点 A 在最后才被处理。后序的特点是“先处理完左子树再处理完右子树最后回来处理自己”所谓“左右根”。这个顺序在很多需要自底向上计算的场景里特别有用比如计算树的高度、删除整棵二叉树、释放内存等都需要先处理孩子再处理父亲。我不建议死记硬背每种遍历结果长什么样而是建议每次递归时都追问一句当前这棵子树它的根什么时候被处理把这层关系想明白递归代码基本不会写错。2.4 递归的时间与空间复杂度一句话能说清二叉树遍历的递归实现时间上每个节点都会被访问一次所以时间复杂度是 O(n)n 是节点总数。无论是前序中序后序都是 O(n)不可能有更快的算法因为每个节点至少要见一面。空间复杂度要稍微分一下。递归的空间消耗主要来自系统调用栈递归深度等于树的高度。最坏情况下如果二叉树退化成一个链表每个节点只有一个孩子递归深度就是 n空间复杂度 O(n)。最好情况下完全二叉树的树高是 O(log n)递归栈深度也就是 O(log n)。所以平均意义下可以用“递归树的深度”来描述空间复杂度。有些人在分析复杂度时把递归函数里每层创建的局部变量也算进去实际上二叉树遍历的递归函数里几乎没有额外局部变量除了参数 node所以只算栈帧开销为主。面试时被问到就答时间 O(n)空间最坏 O(n)平均 O(log n)。不过要注意这个 O(n) 的最坏空间正是递归写法最大的隐患。当树很深比如几万个节点串成一条线时递归会爆栈这就是后面要讲迭代写法的原因。3. 迭代实现把系统栈改成自己的栈3.1 为什么要掌握迭代写法很多同学学会递归后就不想再看迭代了觉得递归又短又好理解。但实际工作或者刷题中迭代你躲不开。首要原因是递归深度有限制。大部分编程语言里函数调用栈是有上限的比如 Python 默认递归深度限制通常是 1000 左右。一棵几万层的退化二叉树递归直接报RecursionError或者对应语言的栈溢出错误。迭代写法用显式的栈或者队列内存分配在你的堆内存里理论上能扛更大规模的数据。其次很多高级题目在递归框架里不好处理比如二叉树的最近公共祖先、迭代式遍历配合剪枝、层序变种题等掌握显式栈模拟之后你对“节点是怎么被路过的”会理解得更深写状态类题目时会顺手很多。最后面试时如果只会递归不会迭代很容易被追问到卡壳。“你的递归空间复杂度是多少”“能不能改成非递归”这两连问就把没准备的人问住了。3.2 前序遍历迭代最容易写的版本前序遍历迭代写起来最顺因为它的顺序和栈的弹出天然契合。前序是“根左右”也就是说我们先要处理根节点然后处理左子树再处理右子树。用栈来模拟时栈是后进先出所以我们希望右子树先被压进去、左子树后被压进去这样左子树先弹出被处理。代码套路def preorder_iter(root): if not root: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) # 先压右再压左出栈顺序才是先左后右 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res来手动模拟一下前面那棵小树初始栈[A]。弹出 A输出 A把 A 的右孩子 C 压入再压左孩子 B现在栈是[C, B]栈顶在右端。弹出 B输出 B压入 B 的右孩子 E再压入左孩子 D栈变为[C, E, D]。弹出 D输出 DD 无孩子。弹出 E输出 EE 无孩子。弹出 C输出 C压入 C 的右孩子 F栈变为[F]。弹出 F输出 F。输出结果是 A B D E C F和递归完全一致。为什么先压右再压左因为栈是 LIFO后压进去的先出来。为了让左子树先于右子树被访问就必须让左子树最后入栈。有几个小细节值得强调。第一不需要用两个栈这个版本就足够了。有些教材上为了格式统一会写一个带状态的双栈版本但前序真的用不着。第二如果题目要求返回的结果是列表而不是就地打印直接把res.append(node.val)当作“处理”操作就行。第三空节点判断放在入栈前做比放在弹出后做要少一些空节点入栈出栈的无效操作。3.3 中序遍历迭代一路向左再回头中序迭代比前序难一些核心难点在于中序要求先访问左子树再访问根节点。但当你从根节点出发时你没法直接知道左子树什么时候结束所以要先沿着左链把节点全部压栈然后一个个弹出处理处理完一个再去看它的右子树。标准写法def inorder_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 从 A 出发一路向左压 A、压 B、压 D。D 的左孩子为空退出内层 while。弹出 D输出 D。cur 指向 D.right为空。进入外层 while栈非空cur 为空。弹 B输出 B。cur 指向 B.right即 E。循环继续cur 是 E。一路向左压 EE 的左孩子为空退出。弹出 E输出 E。cur 指向 E.right为空。外层 while栈非空弹 A输出 A。cur 指向 A.right即 C。循环继续cur 是 C。压 CC 的左孩子为空退出。弹出 C输出 C。cur 指向 F。压 FF 左空。弹出 F输出 F。输出 D B E A C F和递归一致。这个写法的精髓是两个 while 的分工内层 while 负责“潜下去”把根和所有左孩子入栈外层 while 负责“冒上来”弹出一个节点就处理它然后转向右子树。转向右子树之后内层 while 又会把右子树的最左侧路径全部入栈。整个流程就是“压左链、处理栈顶、转右子树、再压左链”的循环。3.4 后序遍历迭代两种主流方案后序迭代是所有遍历里最容易把人绕晕的。递归版只换了一行代码迭代版却没法简单地在上述模板上改因为后序要求左子树、右子树都处理完了才能处理根节点。你弹出根节点时怎么知道它的右子树已经处理过了这是整个问题的核心。方案一前序变体法。前序是“根左右”如果先压左再压右出栈顺序就是“根右左”把这个结果反转一下就变成“左右根”也就是后序。def postorder_iter(root): if not root: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 此时 res 是 根右左反转得到 左右根 return res[::-1]这个方案思路很清晰代码也短。代价是需要额外一次反转不过反转本身是 O(n)不改变整体复杂度。很多同学第一次写后序迭代用这个版本能迅速跑通然后再慢慢理解双栈版。方案二双栈/标记法。更通用也更接近递归语义的做法是用一个栈同时存“节点”和“访问状态”或者用两个栈。这里推荐一种我自己很喜欢的“双色标记法”它可以统一三种迭代写法。双色标记法的核心思路是用一个状态标记区分节点是“第一次出栈、需要展开子树”还是“第二次出栈、直接处理”。可以用元组(node, visited)来实现visited 为 False 表示还没处理过它的子树True 表示可以直接处理这个节点。def postorder_iter_colored(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, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res理解一下第一次遇到一个节点时标记为 False把它弹出后又重新压入标记改为 True然后把右孩子和左孩子按顺序压入。由于栈是后进先出左孩子会被先处理。等到左子树、右子树都处理完后这个标记为 True 的节点再次被弹出满足“左右根”的顺序。这个方法看起来比反转法长一点但它非常贴近递归的语义而且如果把三行入栈顺序调整一下就能直接变成前序和中序非常实用。建议你把三个版本都写一遍体会一下统一性。3.5 三种迭代写法一张表对照遍历核心思想入栈顺序弹出处理时机难点前序处理完根直接进子树右孩子先入、左孩子后入弹出即处理无中序先压左链再弹根根、左孩子依次入栈弹出后转向右子树弹出时处理随后转向右子树记得 cur 回退到右子树后序反转法按“根右左”入栈再反转左孩子先入、右孩子后入先得到根右左再整体反转记录顺序别搞混后序标记法用 visited 状态区分两次弹出根、右、左按逆序入栈第二次弹出时处理状态切换逻辑实际上迭代写法的核心就一件事用栈维护一个“待处理序列”通过入栈顺序控制处理顺序。只要把栈的后进先出性质和递归的处理时机对上三种遍历都不难。4. 应用场景遍历不只是为了打印4.1 二叉树序列化与反序列化的基础序列化就是把一棵树变成一个字符串或数组反序列化就是根据这个字符串恢复出原来的树。这里有一个非常经典的问题给定一棵二叉树的前序遍历序列能否唯一确定一棵树答案是不能。比如序列[A, B]可能是 A 的左孩子是 B也可能是 A 的右孩子是 B两种形态完全不同。但如果你在前序遍历的时候把空节点也标记出来比如用#表示空就能唯一确定一棵树了。具体做法是前序遍历整棵树遇到空节点就记录#遇到非空节点就记录其值。反序列化时同样按前序顺序重建节点遇到#就返回空节点遇到值就创建节点然后递归构建左子树和右子树。可以这样手动模拟树A / \ B C \ D前序加空标记序列是A B # D # # C # #。重建时先创建 A然后读 A 的左子树序列B # D # #再读 A 的右子树序列C # #递归下去就能还原原树。中序和后序遍历加空标记同样能做序列化但因为中序序列本身的特性直接定位根节点时需要额外信息比如前序和后序的配合。在很多实际框架里最常见的序列化方式还是带空标记的前序或后序。层序遍历也能序列化但那是另一套思路了。4.2 表达式树中序遍历还原数学公式表达式树是一种特殊的二叉树叶节点是操作数比如数字非叶节点是运算符比如加减乘除。比如表达式(A B) * (C - D)可以表示成* / \ - / \ / \ A B C D对这棵树做中序遍历得到A B * C - D看起来非常接近原始表达式但括号丢失了。所以单靠中序遍历并不能还原带优先级的完整公式需要根据运算符优先级在输出时额外加括号。后序遍历在表达式树里有更直接的作用对它做后序遍历得到的是A B C D - *也就是后缀表达式。后缀表达式的特点是所有运算顺序都由位置决定不需要括号非常适合用栈直接求值。很多编译原理教材里的逆波兰表达式实际上就是表达式树的后序遍历结果。所以在做题或实际项目里遇到“中缀表达式转后缀表达式”“用栈计算表达式”这类问题本质上都在和二叉树遍历打交道。4.3 后序遍历与自底向上计算后序遍历最典型的应用是处理“先孩子后父亲”的问题。第一类是计算二叉树的高度。求一棵树的高度你得先知道左子树的高度和右子树的高度然后取较大值加一。这个计算顺序天然就是后序先递归左子树、再递归右子树、最后处理当前节点。甚至不用专门写一个遍历函数递归的过程本身就是后序。def tree_height(root): if not root: return 0 left_h tree_height(root.left) right_h tree_height(root.right) return max(left_h, right_h) 1第二类是删除整棵树。如果你不会手动释放每个节点顺序必须是先释放左子树再释放右子树最后释放当前节点。如果你先把当前节点释放了就找不到左右孩子的指针了后面的内存访问就变成了悬空操作。第三类是二叉树路径求和、最近公共祖先等题目。很多“从叶子向上汇总”的问题比如求某个节点到叶子节点的最大路径和本质上都依赖后序的访问顺序。理解了后序是在“第三次路过时处理”你就知道这些题为什么非要用后序不可。4.4 二叉搜索树与中序有序性二叉搜索树BST有一条性质中序遍历的结果是一个严格递增的序列。这是二叉树遍历里最经典、最容易被直接利用的性质。比如给你一棵 BST 和两个节点值让你求它们之间的最小差值。你当然可以每个节点分别去求但更聪明的做法是中序遍历这棵 BST得到一个排好序的数组然后相邻两个数做差取最小值。一次中序就能解决问题复杂度 O(n)。再比如判断一棵树是不是 BST。最朴素的思路是对每个节点判断它是否大于左子树的最大值、小于右子树的最小值但这样可能要反复遍历。一个更优雅的做法就是对它做中序遍历检查结果是否严格递增。只要发现某两个相邻元素与前一个不满足递增关系就说明不是 BST。这个性质在面试题里的出场率极高。如果你手写中序遍历迭代法写得熟很多 BST 中序相关的问题都能很快跑出结果因为迭代法天然不会爆栈也不依赖系统递归限制。5. 实操中的坑与排查实录5.1 递归爆栈当二叉树变成一根长链某次排查一个实际项目里的崩溃问题抛出的异常是调用栈溢出。项目里有一棵从 JSON 数据构建的树数据嵌套深度超过了语言默认的递归上限。代码写得很规整逻辑也对但每层递归都会占一帧栈空间树的深度直接决定了递归深度深度一大就崩。这是所有递归实现共有的隐患和二叉树遍历本身没关系但遍历题里最容易踩到。应对思路有三条。第一判断输入数据的规模是否可控。如果树的深度明确很小比如几百层以内递归写起来最轻松没必要强行上迭代。第二如果深度可能很大用迭代版遍历。上面的前序、中序、后序迭代法都不依赖系统栈实际能处理的数据规模大得多。第三如果递归已经写好了但又不想大改可以把递归转成显式栈的“伪递归”。很多语言里没有原生的尾递归优化最稳的办法还是用栈。顺带补充一个判断标准如果你不确定当前树的深度可以先做一次层序遍历顺便记录最大深度。超过某个安全阈值比如 Python 的 900 层就直接走迭代分支否则用递归。这个方法写起来很笨但在实际生产环境里是有效的保底策略。5.2 中序迭代里 cur 指针迷失方向中序迭代最常见的错误是第一次写完后发现输出结果只输出了根节点左半部分或者抛出了空指针异常。典型错误版本长这样def inorder_iter_wrong(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或者写成了 cur cur.left漏掉cur cur.right会导致弹出的节点处理完后外层循环判断cur为空、栈也为空直接退出右子树完全没遍历。表现出来就是“只输出了左链上的节点”。另一种常见错误是把转向右子树的cur cur.right写在了while cur循环内部导致内层循环陷入死循环或者重复压栈。调试时可以先输出每次弹出的节点再打印 cur 的走向很快就能定位。5.3 后序迭代反转法结果对但步数多了一层用反转法写后序也就是先得到“根右左”再整体反转很多人写完会疑惑这不是“取巧”吗面试官会不会不满意实际答案是这是一个完全正确的解法复杂度也是 O(n)面试时你可以给出这个版本然后补一句“还有一种不反转的双栈标记法我也能写”。关键点在于你能说清楚为什么先“根右左”再反转等于后序。“根右左”怎么得到把前序模板的入栈顺序改一下前序是“右先入、左后入”这里改成“左先入、右后入”弹出顺序就从“根左右”变成“根右左”。然后数组反转就得到“左右根”而后序正好是“左右根”。如果你在写反转法时发现结果反了八成是把入栈顺序弄反了。调试时直接打印中间结果res看看它是“根右左”还是“根左右”一眼就能判断。只要中间结果是“根右左”反转后才正确。5.4 空指针与空树的边界遍历代码里空节点处理看似简单其实最容易在边界上出错。第一root本身为空的情况。前序迭代的if not root: return []、中序迭代的while cur or stack、后序迭代里对空栈的处理都得兼容空树。写代码前先问自己一句这棵树上一个节点都没有结果应该是什么绝大多数题目要求返回空列表而不是报错。第二内部孩子节点为空。前序迭代里入栈前要先判断if node.right和if node.left否则空节点也会入栈弹出后访问.val会报错。当然你也可以不判断直接入栈但在弹出时先判断if not node: continue两种风格选一种并保持一致。第三某些题目要求“按给定分隔符拼接序列”时空节点怎么表示、分隔符和值的转义问题都会被一批初学者忽略。二叉树遍历本身没有这个问题但序列化题目里一定会遇到提前建立这个意识比较好。5.5 快速自查代码的三个问题写完一段遍历代码不需要马上跑数据先问自己三个问题第一如果树为空代码还安全吗第二如果树只有根节点输出只有一个值吗第三如果树是一条左斜线每个节点都只有左孩子遍历顺序是否符合该遍历的定义这三个问题覆盖了绝大多数边界情况。你可以把这套检查法用到所有二叉树题目上其实不只是遍历包括递归求树高、判断平衡二叉树等先过这三个问题再做测试能省很多调试时间。6. 关于练习顺序的两点建议二叉树的遍历是很多算法问题的地基建议刚上手的人先别急着背代码而是找一个小树亲手模拟一遍递归展开的完整流程。前序、中序、后序各模拟一棵树标注出“处理根节点”的时机建立直觉之后再去看代码会顺畅得多。第二个建议是把递归版和迭代版对照着写。先写递归再把递归改成显式栈的迭代版这样做的好处是你能清楚看到每个节点被压栈、弹栈的时机而不是死记迭代代码。以后遇到中序 栈的变体题比如 BST 迭代器、前序和中序重建二叉树你都能快速迁移思路。遍历的代码本身很短但它牵扯出的“递归展开、显式栈模拟、序列化、BST 中序性质”这些内容几乎能串联起所有二叉树核心问题的解决思路。把这一块扎扎实实吃透后面刷树的题目你会感觉顺很多。