二叉树遍历全攻略：递归、迭代、层序模板与踩坑指南

刚开始刷二叉树的时候，我一度以为自己永远记不住这三道题的代码。LeetCode 144、145、94，前序遍历、后序遍历、中序遍历，递归版本三分钟写完，迭代版本一写就卡壳，尤其是中序和后续，每次对着空栈发呆，总觉得逻辑在脑子里是通的，落到代码上就全是问题。后来跟着代码随想录的训练营刷到第十三天，把的递归遍历和迭代遍历从头到尾捋了一遍，又把102题层序遍历加了进来，才真正理解了“遍历顺序”这件事的本质。

这篇东西就是给我的刷题笔记做个沉淀。如果你也处在“递归能写但迭代总卡”的阶段，或者刚准备开始刷二叉树，我尽量把每一行代码背后的为什么讲清楚。文章里有完整的解题模板、复杂度分析，还有我踩过的几个坑，希望能让你少走点弯路。

1. 递归遍历：先想清楚这三件事，前中后序随便写

递归版本是二叉树遍历的起点，也是后边所有写法的根基。LeetCode 144、145、94三道题的递归解法，本质上是在同一个模板里换三行代码的顺序，所以别把三道题当成三个知识点去背，当成一个知识点去理解就好。

1.1 为什么空节点返回是递归的“刹车”

先看最基础的递归模板，拿前序遍历举例：

def preorderTraversal(root): if not root: return [] res = [root.val] res += preorderTraversal(root.left) res += preorderTraversal(root.right) return res

很多人刚写递归的时候，第一反应是“我要用一个全局数组来收集结果”，然后在递归函数里不断append。但你看上面这种写法，每一层递归都返回一个列表，往上层层拼接，最后整棵树的结果就出来了。这个写法的好处是不需要额外定义一个成员变量，函数本身就是纯函数，刷题和面试的时候都不容易写出bug。

这里的if not root不是可有可无的边界条件，它是整个递归的“刹车”。二叉树的递归遍历，本质上是在模拟一条从根节点出发、不断往下走、走到尽头再回头的过程。如果没有这辆“刹车”，函数会一直往None的孩子节点里钻，直到栈溢出。你可以把它理解成递归里的base case：到达空节点，说明这条路走到了头，该掉头回去了。

1.2 三序遍历其实只有一行代码的差别

前序、中序、后序这三个名字，描述的是“根节点”在什么时候被处理：

• 前序：先处理根，再处理左子树，最后处理右子树，简称中左右。
• 中序：先处理左子树，再处理根，最后处理右子树，简称左中右。
• 后序：先处理左子树，再处理右子树，最后处理根，简称左右中。

把三个递归版本放在一起看，区别就更明显了：

def preorderTraversal(root): # 中左右 if not root: return [] res = [root.val] res += preorderTraversal(root.left) res += preorderTraversal(root.right) return res def inorderTraversal(root): # 左中右 if not root: return [] res = [] res += inorderTraversal(root.left) res.append(root.val) res += inorderTraversal(root.right) return res def postorderTraversal(root): # 左右中 if not root: return [] res = [] res += postorderTraversal(root.left) res += postorderTraversal(root.right) res.append(root.val) return res

看到没有，三份代码几乎一样，区别只在于res.append(root.val)这一句的位置：在最前面就是前序，在中间就是中序，在最后就是后序。递归遍历的核心逻辑是统一的：每次处理一个节点，先递归左子树，再递归右子树，根节点的处理顺序决定遍历顺序。

这里我建议大家动手画一棵三层的二叉树，比如1为根、2和3分别为左右孩子、4是2的左孩子，然后分别按三种顺序在图上标注节点被“读到”的顺序。画完之后你会发现，前序是“从上往下，先左后右”，中序是“从左往右，先下后上”，后序是“从下往上，先左后右”。这个直观感觉比背口诀重要得多。

1.3 递归的时间与空间复杂度别只记结论

三道递归解法的时间复杂度都是O(n)，因为每个节点恰好被访问一次。空间复杂度是O(h)，h是树的高度。这个h在最坏情况下可能是n，比如一棵只有左孩子的链式树，递归深度就达到了n；在平衡二叉树里，h大约是log n。

所以递归的空间复杂度不是固定的O(n)，而是取决于树长什么样。很多题解直接写“空间复杂度O(n)”，是为了简化描述，准备的退化成链表的最坏情况。面试的时候如果被追问，能说清楚“递归深度等于树高”这一层，会显得你对本原理是真懂了。

2. 迭代遍历：一个栈怎么同时驾驭前序和中序

递归能解决的问题，迭代基本都能解决，因为递归本身就是在隐式地使用函数调用栈。迭代遍历就是把这个栈从系统手里拿过来，自己显式地维护。这也是LeetCode 144、145、94三道题里最常见的一类进阶考法：不让你用递归，强制你用迭代。

2.1 前序的“右左入栈”为什么能保证顺序

前序遍历迭代写法是三个里面最简单的：

def preorderTraversal(root): if not root: return [] stack = [root] res = [] 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

关键就在最后两个if的顺序：先压右孩子，再压左孩子。因为栈是后进先出，弹出的顺序会和压入的顺序相反。你希望弹出顺序是“先左后右”，就得让右孩子先进栈、左孩子后进栈，这样左孩子会被先弹出。

记住一个口诀：前序迭代就是“中左右，入栈右左”。每一轮循环做的事情其实很单纯：弹出栈顶节点并记录值，然后把这个节点的右孩子、左孩子依次压入栈。栈保证了我们永远先处理左子树这一支，等左子树整支处理完，栈中自然剩下的就是之前压入的各个右子树节点。

我第一次写这个解法时犯过一个错：先压左孩子再压右孩子，结果顺序变成根、右子树、左子树，整棵树的顺序全乱了。后来想明白了栈的特性，这个坑就再也没踩过。

2.2 中序为什么要一路压左链

中序迭代比前序难一个档次，因为它不是简单的“弹出就处理”。看代码：

def inorderTraversal(root): if not root: return [] stack = [] cur = root res = [] while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res

这里最核心的是内层那个while cur循环：它的作用是把当前节点到它的最左叶子这一条链路上的所有节点全部压入栈。为什么？因为中序是左中右，我们必须先处理一棵子树最左边的节点，然后才能往回处理它的父节点。

用一个生活场景来类比：中序遍历就像你要从一棵树的最左下角开始，一格一格往右上方扫过去。遇到每一个节点，你不能立刻处理它，因为它的左子树还没扫完，所以你必须先把节点记在栈里，继续往下钻左子树。钻到最左边没有左孩子了，这时候才从栈里弹出这个最左节点，处理它，然后转向它的右子树，重复同样的逻辑。

整个过程可以概括为三句话：一直往左压栈，弹出并处理，转向右子树。很多教程会把这套写法直接甩给你，但如果你不理解“为什么要一路压栈”，你很难在考场上默写出来。理解了之后，每一次cur = cur.right都是在说：“左子树处理完了，根也处理完了，该轮到我这一侧的右子树了。”

2.3 迭代写法的空指针雷区

迭代写法的bug高发区有两个。

第一个是前序里忘记判断节点是否存在。有些同学会写成：

if node.right: stack.append(node.right) if node.left: stack.append(node.left)

漏掉if判断，直接把空指针压进栈里，循环里就会对None取.val，直接报AttributeError。其实这道题里用if判断还是if root初始化，两种风格都能过，但不能夹在中间造成逻辑混乱。

第二个是中序初始化时，if not root: return []和cur = root这两个条件缺一不可。如果没有最外层的空树判断，while cur or stack在root为空时会直接跳过循环，返回空数组，结果其实也是对的；但如果你想省掉判断，得确保stack的初始状态没问题。代码风格上，我建议保留明确的空树判断，可读性更好，面试的时候也更容易讲清楚。

3. 后序遍历的取巧路径：前序反转法与标记位写法

后序迭代是所有二叉树遍历里最让人头大的一个。网上的主流解法至少有三种，我先讲最取巧的一种，再说一种我自己后来最常用的写法。

3.1 前序反转为什么成立

先看这段代码：

def postorderTraversal(root): if not root: return [] stack = [root] res = [] while stack: node = stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]

你可以把它理解成“前序遍历的镜像版”：前序是“中左右”，这里先按“中右左”的顺序收集结果（所以先压左孩子再压右孩子，让右子树先出栈），最后把整个结果数组反转，就变成了“左右中”，也就是后序遍历。

为什么反转一下就成立了？因为后序是左右中，它和前序的中左右正好是镜像对称的。你按中右左的方式收集，得到的结果反转过来，恰好就是左右中。这个方法在面试里非常实用，因为代码量跟前序几乎一样，只需要改一下两个if的顺序，再在最后加一个反转。

反转整列表的时间复杂度是O(n)，加上前面遍历的O(n)，整体还是O(n)，不影响大O级别。空间上多了一个res数组存结果，这部分本来就是答案需要占用的空间，不算额外开销。

3.2 标记位写法：用None统一三种遍历

除了前序反转，还有一种“标记位”写法，也是代码随想录教程里重点推荐的路子。它的核心思路是：每次把节点压入栈时，同时在它后面压一个标记，当这个标记被弹出时，说明这个节点的左右子树已经处理完了，可以输出这个节点本身了。

def postorderTraversal(root): if not root: return [] stack = [root] res = [] while stack: node = stack.pop() if node: stack.append(node) stack.append(None) # 标记，表示node已经可以输出了 if node.right: stack.append(node.right) if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res

你可能会问，前序和中序是不是也能用同一种套路？完全可以，只需要调整节点、标记、左右孩子入栈的顺序。标记位写法的本质，是用一个额外的None元素模拟递归的“函数返回”动作。递归里，函数处理完一棵子树后会自动回到上一层；迭代写法没有这个自动机制，所以需要自己往栈里塞一个“返回点”。

这种写法的好处是模板统一，三种遍历只需要调整压栈顺序。坏处是代码看起来有点绕，第一次看容易懵。我建议先用前序反转法把后序遍历跑通，等对栈的操作足够熟悉了，再来体会标记位写法的精妙。

3.3 我后来为什么倾向于标记位写法

说实话，如果只是为了AC一道题，前序反转法更短、更不容易写错。但我后来在做一些二叉树相关的综合题时发现，标记位写法更接近递归的思考方式：它的入栈顺序是从“最迟到处理”的逻辑倒推的，只要把递归里“左、根、右/左、右、根”的访问顺序翻译成入栈顺序就行，不容易陷入“中序那个while循环怎么控制”的困惑里。

另外一点，标记位思路对理解其他需要遍历顺序的题目也有帮助。比如二叉树最近公共祖先、二叉树展开为链表这类题目，不要求纯按后序输出，但需要用“先孩子后自己”的处理次序，标记位写法体现出的“延迟处理”思想就很有用了。

这里也提一句，网上还能看到“双栈法”解决后序遍历，思路是先遍历得到中右左，再用另一个栈反转。原理和前序反转法完全一样，我个人觉得有一个就够用了。

4. 层序遍历：一个队列解决的不只是102这道题

LeetCode 102是一道“看起来基础、实际上能延伸出一大堆题”的典型代表。层序遍历的写法套路很固定，但理解清楚它为什么用队列，以及怎么控制“一层”的范围，比背代码重要得多。

4.1 为什么层序必须用队列

先看基础代码：

from collections import deque def levelOrder(root): if not root: return [] q = deque([root]) res = [] while q: level = [] for _ in range(len(q)): 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 res

层序遍历和前中后序的最大区别是：它不是深度优先，而是广度优先。深度优先用栈，因为要一条路走到黑再回头；广度优先用队列，因为要一层一层地平推。这是“用什么数据结构”的根本依据，不要死记。

想象一下，你手头有一个队列，初始时只有根节点。你把根节点从队头取出来，把它左右两个孩子从队尾放进去。第二轮循环，队列里的两个孩子会被依次取出，同时它们各自的孩子又会被放进队尾。每一轮，队列里装的恰好就是某一层的节点；你从队头取走老节点，从队尾放进去新节点，先进先出，自然保证了“同一层按从左到右的顺序输出”。

4.2 用size固定每层范围

初学者容易写错的地方是：不知道每层有多少个节点，直接把while q写成while q，把所有节点一股脑输出，层与层之间就混在一起了。

上面代码里的for _ in range(len(q))是控制一层的边界。关键点在于，进入for循环时，len(q)记录的是当前层节点的数量；循环过程中往队列里push进下一层的节点，len(q)已经变了，但range(len(q))是在进入循环前计算好的，所以它只遍历当前层的节点数。

举个例子，队列里第一层只有根节点，len(q)是1，for循环只跑一次；处理根节点时push进两个孩子，队列变成2个节点；进入下一轮，len(q)是2，for循环跑两次，把两个孩子都取出来，同时push进四个孙子节点。这样每一轮都精确地处理一层，不会越界。

4.3 从102延伸出去的同源变体题

102这道题看着简单，却是一整类题目的基础。层序遍历的框架一旦熟练，下面这些题你都可以用同一套核心代码改改：

这些题目我在刷的时候最大的感受是：102的代码框架就是一个“遍历引擎”，引擎不动，只改“每层处理逻辑”那一小块，就能应对一大片题目。所以别把这题当孤立题刷，要在脑子里把它当成“层序家族”的底座。

5. 刷这套题时我踩过的坑和最后的建议

这几道题的坑不算多，但如果没人提醒，确实容易在细节上浪费不少时间。我把自己踩过的、身边朋友也踩过的几个问题集中说一下。

5.1 空指针错误：报错信息的另一层含义

很多初学者在LeetCode上提交二叉树相关的题，会遇到“AttributeError: 'NoneType' object has no attribute 'val'”这类报错。这个报错在网络热词里被反复讨论，说明它不是个例。

这个错误绝大多数情况不是LeetCode的坑，而是你没有处理空节点。比如层序遍历里，你没判断node.left是否为空就直接node.left.val，自然报错；递归里base case没写全，递归到None节点上还去访问val，也会面对同样的错误。

我的建议是：每道二叉树题的代码写完后，先自己检查一遍“所有取.val的地方，它的对象有没有可能是None”。养成了这个习惯，这类报错基本能消除90%。剩下的10%，多半是题目给你的树本来就是空树，记得开头补一句if not root: return []就行。

5.2 二叉树的“空位”问题

刷层序题的时候，有人会遇到一个困惑：LeetCode题目里用数组表示的二叉树，比如[3,9,20,null,null,15,7]，这个null是不是一个真实节点？

不是。层序数组里的null只是用来占位，表示这个位置没有节点。但在实际代码里，树的节点结构里根本不存在“值为null的节点”，只有“这个引用指向None”。所以你在做层序遍历时，queue里永远不会出现null占位符，只会在push孩子时跳过None。

如果题目要求你按照数组来还原一棵树，那另当别论；但LeetCode 102、144、145、94这些题输入都是已经建好的树对象，不是数组，别把数组的null概念带进代码逻辑里。

5.3 关于刷题顺序和训练营节奏的体会

代码随想录这套训练营的安排，第13天集中做二叉树遍历，是有意为之的。前面链表、哈希表、字符串那些题目，主要锻炼的是对线性结构的处理；到了二叉树，思维方式要从“线性”切换到“树形”，递归思想正式上场。如果前面基础没打牢，这一天的题目会特别吃力。

按训练营的节奏，第一天先把递归遍历写熟，第二天再上迭代，第三天再碰层序，这个梯度我个人体验下来是比较舒服的。不要第一天就想把四种遍历全部拿下，大脑会把相似代码混淆起来，第二天全忘干净。

我个人的体会是：二叉树遍历这四道题，最重要的不是“能写出代码”，而是“能解释为什么要这么写”。面试时候官不会只让你写前序递归，他很可能会追问“不用递归怎么写”“层序用队列还是栈”“空间复杂度是多少”。所以刷的时候多问自己几个为什么，比多刷一遍题更有价值。这套题真正吃透之后，后面遇到二叉树的属性题、路径题、构造题，你会发现自己上手快很多。祝卡在递归和迭代之间的你，早日把这层窗户纸捅破。