有些东西理论上看十遍不如亲手推一遍二叉树遍历就是最典型的例子。很多初学者一开始被前序、中序、后序这三个词弄得晕头转向刷题时也是背了忘、忘了背。其实这些遍历的本质非常简单——就一句话访问根节点的时机不同。但就是这么一句话背后牵扯到递归理解、栈的运用、结果规律、树的还原等一系列问题一步没想通后面全卡壳。这篇文章我打算从定义讲到递归从递归讲到手写栈迭代最后再聊聊 Morris 遍历和由遍历结果重建二叉树。无论你是刚接触数据结构、正在准备面试还是在工作中需要手写树的遍历逻辑这篇文章都能给你一条完整、可复现的思路。我会把每一步的为什么讲清楚而不是只扔给你几段代码。1. 三种遍历到底在遍历什么1.1 一切的起点根、左子树、右子树二叉树的结构本质上就三个部分组成根节点、左子树、右子树。这里的关键认知是左子树和右子树本身也是二叉树所以它们各自也有自己的根节点。这就像一个公司组织架构部门下面还有子部门每个子部门都有自己的负责人。遍历一棵二叉树说白了就是把每个节点都访问一遍但不能乱访问得按某种规矩来。而这个规矩只有三种基本选择先看根节点根再看左子树左再看右子树右根、左、右这三个字的排列组合按顺序固定下来就得到了三种经典遍历前序遍历根 → 左 → 右中序遍历左 → 根 → 右后序遍历左 → 右 → 根注意左永远在右前面这是所有遍历的铁律因为二叉树本身定义了左子树在前、右子树在后的逻辑顺序。变化的只有根节点的访问时机。我用一个类比帮你记假设你要参观一个家族宗祠中间供着祖宗牌位根左边一排是长房后人左子树右边一排是次房后人右子树。前序遍历是进门先拜祖宗再去左边最后去右边中序遍历是先逛左边回来拜祖宗再去右边后序遍历是把两边都逛完了最后才回来拜祖宗。这就是三种遍历的全部秘密。1.2 为什么叫前序而不是根序很多初学者问既然前序的实质是根最先被访问为什么不直接叫根序遍历这个问题问得好答案在于术语的约定俗成。前序Preorder中的前官方解释指的是根节点在其左右子树之前被访问。这个命名源自英文Pre- 表示在前In- 表示在中间Post- 表示在后直译过来就是根在前、根在中、根在后的意思。理解这一点很重要因为后续你会接触到各种变体比如已知前序 中序重建二叉树这类题。如果你心里始终清楚前序就是根最先被访问那么看到前序序列的第一个元素永远整棵树的根你就不会觉得奇怪了。我建议你在学习时自己画一棵简单的树手动把三种遍历的结果都写出来再对照代码验证一遍。这个过程虽然简单但对建立直觉非常有效下面这张表就是我当时用来对照的遍历方式访问顺序根的位置典型应用前序遍历根左右第一个元素复制树、序列化中序遍历左根右中间位置二叉搜索树有序输出后序遍历左右根最后一个元素删除树、自底向上计算当你把这张表刻进脑子里后面看到任何题都能条件反射地调出对应的遍历框架。2. 递归实现三行代码的事情为什么你总觉得难2.1 递归的视角把树拆成根 两棵小树递归实现三种遍历代码量极少核心逻辑几乎一模一样。我先给出完整的 Python 代码不要觉得简单重点是理解递归函数是怎么自动帮你遍历完所有节点的。# 定义二叉树节点 class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 前序遍历根 - 左 - 右 def preorder(root): if root is None: return [] result [root.val] result preorder(root.left) result preorder(root.right) return result # 中序遍历左 - 根 - 右 def inorder(root): if root is None: return [] result inorder(root.left) result [root.val] result inorder(root.right) return result # 后序遍历左 - 右 - 根 def postorder(root): if root is None: return [] result postorder(root.left) result postorder(root.right) result [root.val] return result你看三种遍历的唯一区别就是把根的值放进结果列表这一行代码放在哪个位置。放在最前面就是前序放在中间就是中序放在最后就是后序。如果去掉这一行三个函数看起来几乎一样。那为什么初学者会觉得递归难问题出在跟踪递归过程上。人脑不擅长层层嵌套的调用所以你会试图跟着代码一步步进去再出来很快就晕了。递归的正确打开方式是信任你的函数——你不需要一步步展开所有调用你只需要相信inorder(root.left) 一定能返回左子树上所有遍历结果至于它是怎么做到的那是它自己的事。这种思维方式叫递归信仰recursive leap of faith是分治思维的核心。2.2 base case 到底该返回什么一个很容易出错但又不至于让人卡住的小问题递归的终止条件base case该返回什么很多人的第一反应是返回 None但这会在上一层调用时导致result None直接报错。正确做法是返回空列表[]这样result []什么都不加循环自然停止。注意如果你是在力扣LeetCode之类的平台上做题也可以用空节点直接返回 None再在函数开头判断的写法但这需要你在每次递归前都判断子节点是否为空代码会冗余不少。统一用空列表作为 base case 更简洁。还有一个很多人踩过的坑把递归函数写成边遍历边打印没问题但如果你想返回一个列表就不要在递归里反复result.append(root.val)然后又递归调用那样每个递归分支都会创建新的列表最后返回的结果会被层层拼接容易出错。最稳的写法就是上面那种每层递归返回一个列表由上层拼接。虽然性能上不是最优会产生额外拷贝但对于理解和刷题来说足够了。我用斐波那契数列来类比递归思想算 fib(5) 时你不需要真正去展开 fib(4) 和 fib(3) 的每一层调用你只需要知道fib 函数能算出我给它的那个数的值。二叉树遍历也是一样的递归函数就是那个能遍历一棵树的黑盒子你只需要调它不需要看它内部每一步在干嘛。一旦你把这个思维转过来递归遍历这道坎就过去了。3. 迭代实现手动模拟栈把递归的底裤翻出来3.1 为什么递归能工作因为系统帮你维护了一个栈递归之所以能执行是因为操作系统在底层为你维护了一个调用栈——每次递归调用都往栈里压入一个新的帧保存了当前函数的局部变量和执行状态函数返回时弹出这个帧。所以递归遍历的本质是用系统栈来记录我走到哪一步了接下来该处理哪棵子树。那么如果不用递归我们自己显式地用一个栈来模拟这个过程就形成了迭代遍历。迭代遍历之所以重要有两层原因第一递归一旦深度太深比如树的高度上万系统调用栈会溢出程序直接崩溃第二很多面试官会专门考察你是否理解遍历的底层逻辑让你在不使用递归的前提下完成遍历。3.2 前序迭代最简单的一版前序遍历的访问顺序是根 → 左 → 右。用栈模拟的核心思路是每访问一个节点先把它的值记下来然后先压右子节点再压左子节点。为什么先压右因为栈是后进先出的右子树先进栈、左子树后进栈下一轮循环时左子树先出栈正好满足先左后右的顺序。def preorder_iterative(root): if root is None: return [] stack [root] result [] 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你可以用这个思路去推演一棵小树假设树的结构是1 - 2左 - 3右。初始栈里有1弹出打印 1压入 3 和 2此时栈从顶到底依次是 2、3。下一轮弹出 2打印压入 2 的左右子节点本例没有。再弹出 3打印。最终结果是[1, 2, 3]正确。这个写法的优点是非常直观几乎不用动脑缺点是不够通用——它只适用于前序。如果你拿去改造成中序会发现完全行不通因为中序要求根在中间输出你必须先把所有左子节点压栈然后才能弹根。这正是中序迭代要解决的核心问题。3.3 中序迭代一路向左弹出来再看右边中序遍历的顺序是左 → 根 → 右。迭代思路是我个人认为最优雅的外层循环控制和当前节点本身内层循环负责把当前节点一路向左的所有左子节点全部压栈直到为空。当没有左子节点时弹出栈顶这一定是当前这个子树的最左下节点也就是最左边的根记录它的值然后让当前节点指向它的右子节点继续循环。def inorder_iterative(root): stack [] result [] cur root while stack or cur: # 一路向左把路径上的节点全部入栈 while cur: stack.append(cur) cur cur.left # 栈顶就是最左边且尚未处理的节点 node stack.pop() result.append(node.val) # 关键转向右子树 cur node.right return result这个代码为什么对你可以把整棵树理解成最左边的一列节点依次入栈然后每弹出一个就相当于处理了一个局部根同时马上尝试访问它的右子树。右子树又是一个完整的树所以又重复一路向左的逻辑。整个过程中栈里存放的始终是尚未访问根节点的那些祖先们。还是用例子推演树结构2根 - 1左 - 3右。初始 cur2压入 2再压入 1直到左为空。此时栈底到顶是 [2, 1]。弹出 1记录cur 指向 1 的右空。外层循环再判断stack 非空进入内层 whilecur 为空不执行弹出 2记录cur 指向 3。内层 while 压入 3弹出 3记录。最终结果[1, 2, 3]正确。3.4 后序迭代最烧脑的一版但有个偷懒妙招后序遍历的顺序是左 → 右 → 根要求根在最后被访问。直接模拟这个顺序很麻烦因为当你从栈里弹出一个节点时你没法判断是该访问它了还是右子树还没处理完。所以常见解法有两种解法一双栈思路 / 标记法如果你不追求极致的空间优化可以在栈里存一个标记(node, visited)。第一次弹出时标记为未访问把(node, False)换成(node, True)再压回去同时把它的左右子节点按先左后右压入。第二次弹出时标记为已访问记录下来。def postorder_iterative(root): if root is None: return [] stack [(root, False)] result [] while stack: node, visited stack.pop() if visited: result.append(node.val) else: # 后序左 - 右 - 根压栈顺序反过来根、右、左 stack.append((node, True)) if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) return result解法二利用前序逆序如果你观察一下后序遍历的结果会发现它正好等于根 → 右 → 左遍历结果的逆序。这里的根 → 右 → 左本质上就是前序遍历的一个变体先访问根然后先走右子树再走左子树。所以我们可以套用前序迭代的框架只要把压栈顺序反过来先压左再压右最后把整个结果列表反转即可def postorder_iterative(root): if root is None: return [] stack [root] result [] while stack: node stack.pop() result.append(node.val) # 前序是先右后左压栈这里反过来先左后右 if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 逆序输出 return result[::-1]这种做法是我个人最推荐的因为它代码量最小且不容易出错。唯一的缺点是最后多了一次反转列表的操作但在工程上完全可以接受。等你理解了这两种写法后序迭代对你的阻碍就彻底消失了。实操心得迭代遍历的核心是搞清楚栈里存的是什么。前序的栈里存的是接下来要处理的节点中序的栈里存的是等待右子树处理完后才能弹出的祖先后序的栈里存的是带状态的节点。一旦你把栈的语义定义清楚代码就不会写错。4. 从遍历结果里看出门道规律与应用4.1 前序、中序、后序各自隐藏的信息当你写出三种遍历的结果静下心来看这些序列会发现很多规律。这些规律不只是考试题更是工程中设计算法的基础。前序序列第一个元素一定是整棵树的根。这很好理解前序先访问根。进一步前序序列中任意一个节点之后紧接着的一段是以它为根的左子树的前序序列、再往后是右子树的前序序列虽然你无法单纯从前序中分清左右子树的分界在哪里但全局第一个是根这个信息是确定的。中序序列如果这棵树是二叉搜索树BST那么中序遍历的结果就是一个严格递增的有序序列。这是 BST 最重要的性质也是验证一棵树是不是 BST的经典解法中序遍历后检查是否有序即可。另外中序序列中根节点的位置天然地把序列分成了左子树元素和右子树元素两部分——正是因为这个性质由前序 中序或后序 中序重建二叉树才成为可能。后序序列最后一个元素一定是整棵树的根。对于任何树都是如此。同时后序的左右根特性决定了你只有处理完所有孩子节点后才会拿到父节点的值这种自底向上的顺序特别适合做树形 DP和自动释放内存这类需求。我把这些规律整理成一张速查表已知序列能确定什么典型用途前序第一个元素是根序列化、复制树中序二叉搜索树中有序验证 BST后序最后一个元素是根删除树、树形 DP前序 中序可唯一重建二叉树LeetCode 105后序 中序可唯一重建二叉树LeetCode 106前序 后序一般不能唯一重建除非树是满二叉树4.2 为什么前序 后序不一定能重建二叉树这个问题很多初学者想不明白我有前序和后序吻合一棵树的所有父子约束为什么还不能唯一确定树的结构关键原因在于单子树的情况下你分不清它是左子树还是右子树。举个例子一棵只有两个节点的树根 左孩子得到的前序是[1, 2]后序是[2, 1]根 右孩子得到的前序也是[1, 2]后序还是[2, 1]。你看两种完全不同的树结构却产生了完全相同的遍历序列。这说明前序和后序合在一起丢失了左右的方位信息。而中序为什么能补救因为中序序列中根的左边永远是左子树、右边永远是右子树这个方位信息是恢复树形结构的关键。重建二叉树的标准思路其实很清晰从前序/后序中确定根拿根去中序里做切分。假设用前序 中序重建已知前序第一个是整棵树的根把这个根的值拿到中序序列中找到它的位置左侧的全部元素就是左子树的中序序列右侧的全部元素就是右子树的中序序列。再回到前序序列中中序左子树序列的长度对应前序序列中紧随根之后的同长度子段这就是左子树的前序序列。左右子树都拿到了前序 中序两段就可以递归重建。def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) # 找到根在中序中的位置 idx inorder.index(root_val) # 左子树的长度 left_len idx root.left build_tree(preorder[1:left_len1], inorder[:idx]) root.right build_tree(preorder[left_len1:], inorder[idx1:]) return root这段代码就是 L105 的递归写法每次递归都消耗掉一个根节点并缩小序列的范围。同样的思路把从前序取根换成从后序取根取最后一个元素就变成了 L106 的后序 中序重建。这里有一个工程优化点用inorder.index()每次都要线性查找根的位置整棵树重建的时间复杂度会退化到 O(n²)。你在竞赛或面试时可以先用一个哈希表把值和下标存起来每次 O(1) 定位根整体降到 O(n)。4.3 层序遍历别和深度遍历搞混写到这里顺带提一下层序遍历因为很多人刚学三种 DFS 遍历时容易把层序遍历BFS也混进来形成认知负担。层序遍历的顺序是按层级从上到下、每层从左到右它使用队列queue而非栈stack每次处理一层而不是一条路径深挖到底。它和前、中、后序遍历的关系是平行的不是替代关系。在具体应用中层序遍历常用来求树的最大宽度、找最底层最左节点而前中后序更适合处理路径、子树关系、递归结构的问题。理解它们的区别比背一百道题更有价值。5. 从递归到 O(1) 空间Morris 遍历到底在干嘛5.1 线索化思路把空指针利用起来递归遍历需要系统栈迭代遍历需要显式栈两者空间复杂度都是 O(h)h 为树高。那有没有可能做到 O(1) 空间理论上可以这就是 Morris 遍历。Morris 的原理不复杂但初次接触会觉得设计很精巧。Morris 的核心思想是线索化对于一个有左子树的节点找到它的左子树中最右边的节点也就是中序遍历中它的前驱节点然后把前驱节点的右指针临时指向当前节点。这样在遍历完左子树之后可以顺着这个指针回到根节点不需要用栈保存祖先信息。当这个临时指针用完后再把它置回 None恢复树的原样。5.2 Morris 中序遍历的完整实现我给你一个 Morris 中序遍历的实现这是最经典、也好理解的一版def morris_inorder(root): result [] cur root while cur: if cur.left is None: result.append(cur.val) cur cur.right else: # 找到左子树的最右节点前驱 pre cur.left while pre.right and pre.right ! cur: pre pre.right if pre.right is None: # 建立线索把前驱的右指针指向 cur pre.right cur cur cur.left else: # 线索已存在说明左子树已遍历完 pre.right None result.append(cur.val) cur cur.right return result这段代码只有两个分支、一个内层循环但可能会绕。我用文字帮你捋一遍主流程如果当前节点没有左子树直接访问它然后跳右子树。如果有左子树先找到左子树的最右节点 pre。如果 pre 的右指针为空说明还没建立线索把 pre.right 指向当前节点当前节点移到左子节点这是向下走为以后回家做准备。如果 pre 的右指针已经指向当前节点说明左子树已经遍历完了这时把 pre.right 恢复为空拆掉线索访问当前节点然后当前节点向右移动。空间确实是 O(1)因为只用了两个指针变量。时间上每个节点最多被访问两次一次建线索、一次拆线索均摊下来还是 O(n)。在工程中这种遍历通常用于内存受限的环境比如嵌入式系统里遍历一棵不能修改结构的树。5.3 什么时候该用 Morris什么时候别用Morris 虽然空间很省但它有一个明显的缺点遍历过程中会临时修改树的结构哪怕最后会恢复。如果在你遍历的同时有其他线程也在读这棵树就会出现竞争问题。另外Morris 的可读性远不如递归和迭代维护成本高。我的建议是面试时主动提一嘴我可以讲 Morris 遍历的思路但代码题优先选迭代法真正生产环境中如果树是不可变的immutable遍历时不允许改指针那就不能用 Morris。这个权衡你心里要有数。6. 实操中的常见错误与排查技巧6.1 手写遍历最容易翻车的三个位置在我带过的新人和刷题群里下面这几个错是出现频率最高的。错误一递归 base case 写错。有时候返回None然后在函数开头写if root is None: return []没有统一有时候返回[root.val]导致叶子节点被重复处理。这类错误的典型现象是结果列表里出现 None 或者重复数字。排查方法很简单画一棵只有 1~2 个节点的小树手写预期结果再对照代码输出。错误二中序迭代时忘了在弹出节点后更新 cur。少了cur node.right这一行程序会陷入死循环或漏掉右子树。具体表现是每次弹完就直接从栈顶继续而栈里没有压入任何新节点最终提前结束。排查方法是打印每一步的栈内容和 cur 指向肉眼就能看出逻辑断了。错误三后序迭代中左右子树的压栈顺序搞反。在标记法里如果你把右子树先压入会导致它先被处理结果就错了。解决这类问题的通用技巧是明确你每一次弹出节点时希望谁先被处理利用栈的后进先出特性反推压栈顺序。6.2 一行日志打天下用最小用例验证调试树相关代码最有效的工具不是调试器而是最小用例 逐步打印。我的习惯是定义一棵固定的小树比如1的左孩子是2右孩子是3然后把每个关键循环的前三步打印出来看是否符合预期。一旦最小用例通过再压测随机生成的大树验证正确性。这个思路适用于任何算法题但对树尤其有效因为树的结构可视化之后问题非常直观。我还见过一种常见的错误观念认为代码跑通了就等于理解了。其实不少人是靠试错把代码凑对的并没有真正理解栈的进出时机。我的建议是每写完一种遍历就手动推演一遍三个节点的简单树在代码里加一行print(stack)或加一个变量记录执行流程直到你不需要跑代码也能脑内模拟出栈的变化。这个过程重复三遍你基本就再也不会忘了。6.3 从背代码到随心写的三个练习阶梯如果你现在还是靠着记忆写遍历我强烈建议你按下面的阶梯做针对性练习第一步只看伪代码不让看语言实现自己动手写递归版三种遍历。核心目标是理解根放在不同位置。第二步不看任何参考自己写前序和中序的迭代版。如果卡住了画栈的变化图然后再写一遍。第三步自己推演后序的标记法然后尝试写出逆序法利用前序变体 反转最后再挑战 Morris。这三个阶梯走完二叉树遍历基本就被你焊死了。后续无论遇到什么树相关的题比如最近公共祖先、树的直径、路径总和你都是站在一个非常扎实的基础上。从这里再往后你需要的就不再是遍历怎么写而是遍历的结果怎么用——那是另一个层面的算法思维问题但地基已经打牢了。