1. 三种遍历方式的定义与递归实现1.1 遍历时到底在走什么路线先问一个问题一棵二叉树你不是用眼睛看而是让程序去把每个节点都访问一遍你会怎么走大多数教材会把三种遍历讲成三条口诀前序是根左右中序是左根右后序是左右根。但我见过太多人背了口诀还是会写错原因在于没有理解这三条路线到底长什么样。想象你站在一棵树的根节点上手里拿着一支笔沿着树的边往下走。无论哪种遍历你走的物理路径其实是同一条——从根出发绕着整棵树的外轮廓走一圈最后回到根。区别只在于你在什么时机记录当前节点。第一次经过节点时记录就是前序遍历第二次经过节点时记录就是中序遍历对左子树来说是从左子树回来时对右子树来说是刚要从它下去时但统一理解成从左子树返回之后、进入右子树之前第三次经过节点时记录就是后序遍历这个三次经过的类比是我上课时给学生讲得最多的一种解释。它把三个看似割裂的规则统一成了一件事。你不需要背口诀只需要知道递归函数在什么时候执行打印语句。1.2 递归实现写起来有多简单递归版本的三种遍历几乎可以互相当模板用差别只是visit语句的位置。我用 C 语言写一遍注释里标出了关键行typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 前序遍历根 - 左 - 右 void preorder(TreeNode *root) { if (root NULL) return; // 递归出口 printf(%d , root-val); // 第一次经过时访问 preorder(root-left); preorder(root-right); } // 中序遍历左 - 根 - 右 void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); // 第二次经过时访问 inorder(root-right); } // 后序遍历左 - 右 - 根 void postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-val); // 第三次经过时访问 }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 [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if root is None: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if root is None: return [] return postorder(root.left) postorder(root.right) [root.val]写递归有个容易忽略的细节递归出口必须先判空。很多人脑子里想着根左右结果写出if (root-left)之类的条件判断画蛇添足反而容易在某个子树为空时崩溃。事实上递归遍历的代码就是空节点直接返回这一条加上三行调用的组合没有任何玄机。递归写法虽然简单但它有一个先天弱点当树的深度足够大时函数调用栈会爆掉。一棵严重倾斜的树节点数几万层递归就直接栈溢出错给你看。这也是为什么非递归写法在工程和面试里都是必考内容。2. 非递归遍历面试和工程里的硬骨头2.1 为什么非要用栈模拟递归的本质是系统帮你维护了一个调用栈。你每次调用函数系统就把当前的状态压栈返回时再弹栈。非递归遍历要做的事情就是把这个系统栈换成显式栈由你自己控制入栈、出栈和访问时机。用栈模拟遍历最关键的一点是搞明白访问节点和压入栈是两件不同的事。很多初学者写迭代版前序写着写着就混乱了——把打印语句放错了位置输出结果就完全不对。我建议你先在纸上画一棵三层的二叉树然后模拟一遍前序迭代的完整过程根节点入栈弹出栈顶节点 p访问打印p先把 p 的右孩子入栈再把 p 的左孩子入栈重复第 2 步直到栈为空为什么要先压右孩子再压左孩子因为栈是后进先出的。你想让左孩子先被访问就得让它后入栈。这一步理解透了前序和中序的迭代写法就都好办了。2.2 前序和中序的迭代写法前序迭代版直接照着上述步骤写void preorderIter(TreeNode *root) { if (root NULL) return; TreeNode *stack[1000]; int top -1; stack[top] root; while (top 0) { TreeNode *node stack[top--]; printf(%d , node-val); // 先压右后压左保证左子树先出栈 if (node-right) stack[top] node-right; if (node-left) stack[top] node-left; } }中序迭代就没这么直观了核心思路变成一路往左走把路过的节点全部入栈走到最左边后弹栈访问然后转向右子树。void inorderIter(TreeNode *root) { TreeNode *stack[1000]; int top -1; TreeNode *cur root; while (cur ! NULL || top 0) { // 一路向左把路径上的节点压栈 while (cur ! NULL) { stack[top] cur; cur cur-left; } // 弹栈并访问 cur stack[top--]; printf(%d , cur-val); // 转向右子树 cur cur-right; } }这个版本的退出条件是cur ! NULL || top 0两个条件缺一不可。如果你只写top 0一开始栈是空的循环直接不进去如果只写cur ! NULL等 cur 走到最底层 NULL 的时候循环就结束了但栈里还压着一堆没访问的节点。中序迭代的另一种等价写法是先全都压进去再逐个弹出并处理右子树但上面这版是最常见、也最不容易写错的。我面试候选人时只要看到他能把中序迭代的cur指针什么时候更新讲清楚基本就能判断他的二叉树基础是扎实的。2.3 后序迭代两个栈的偷懒方案后序迭代是三种里面最麻烦的因为根在最晚访问但你又不能像中序那样通过从左子树返回来确定访问时机。后序的难点在于一个节点访问完左子树之后不是马上访问它而是要先去访问右子树等右子树也访问完了才轮到它。我记得自己当年在笔试里被这道题卡了十分钟后来学到一种特别优雅的解法两个栈。思路是这样后序遍历是左-右-根如果我把访问顺序倒过来看就是根-右-左。而这个根-右-左其实就是前序遍历的一种变体——前序是根-左-右把左右孩子的入栈顺序对调一下就能得到根-右-左的序列存到另一个栈里最后再倒出来就是左-右-根的后序序列。void postorderIter(TreeNode *root) { if (root NULL) return; TreeNode *s1[1000]; // 用于遍历 TreeNode *s2[1000]; // 用于反转 int top1 -1, top2 -1; s1[top1] root; while (top1 0) { TreeNode *node s1[top1--]; s2[top2] node; // 先存到 s2 // 注意这里先压左再压右和前序相反 if (node-left) s1[top1] node-left; if (node-right) s1[top1] node-right; } // 把 s2 依次弹出就是后序遍历 while (top2 0) { printf(%d , s2[top2--]-val); } }两栈方案的空间复杂度是 O(n)代码逻辑清晰不容易写错面试时是一个很好的保底方案。追求单栈写法的朋友可以试一下记录上一次访问节点的思路设一个prev指针每次弹出栈顶时判断——如果当前节点的右子树为空或者右子树已经被访问过就可以放心访问当前节点否则先不访问把当前节点重新压回去转去处理右子树。这个写法更难理解实际工程中用得少这里就不展开贴代码了建议你拿着两栈方案做基准再去理解单栈版本。3. 从遍历序列还原二叉树一道高频题背后的原理3.1 为什么必须要有中序热词里有一个知道二叉树先序和中序 确定树的样子很多同学刷题时遇到过这类题。它的标准问法是给定一棵二叉树的前序遍历序列和中序遍历序列重建这棵二叉树。先给结论前序 中序可以唯一确定一棵二叉树后序 中序也可以唯一确定一棵二叉树但前序 后序不行。原因可以从定义里推出来前序序列的第一个元素一定是根节点中序序列中根节点左边的所有元素属于左子树右边的所有元素属于右子树这两条信息一结合你就能知道左子树有多长、右子树有多长而前序 后序只告诉你根在哪一头却给不出左右子树的分界点。比如前序是[1,2]后序是[2,1]这棵树既可以是 1 的左孩子是 2也可以是 1 的右孩子是 2无法区分。我教学生的时候喜欢用一个生活类比前序告诉你先见老板再看员工后序告诉你先看员工再见老板但只有中序告诉你哪些员工归哪个老板管。没有这个归属关系树就重建不出来。3.2 手动还原的方法和代码思路手动还原的思路其实就是一个递归分治从前序序列中取出第一个元素作为根在中序序列中找到这个根的位置左边是左子树的中序序列右边是右子树的中序序列根据左子树中序序列的长度从前序序列中切出左子树的前序序列和右子树的前序序列递归重建左右子树举一个具体例子。前序序列[3, 9, 20, 15, 7]中序序列[9, 3, 15, 20, 7]。先看前序第一个元素3它是根。在中序里找3的位置发现它在索引 1 处。那么左子树的中序是[9]右子树的中序是[15, 20, 7]。左子树中序长度为 1所以前序中根后面的 1 个元素[9]是左子树的前序剩下的[20, 15, 7]是右子树的前序。递归处理下去整棵树就出来了3 / \ 9 20 / \ 15 7用 C 语言实现时比较经典的写法是递归 哈希表记录中序位置#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 在中序序列中查找根节点的位置 int search(int *inorder, int start, int end, int val) { for (int i start; i end; i) { if (inorder[i] val) return i; } return -1; } TreeNode* buildTreeHelper(int *preorder, int *inorder, int preStart, int preEnd, int inStart, int inEnd) { if (preStart preEnd) return NULL; TreeNode *root (TreeNode *)malloc(sizeof(TreeNode)); root-val preorder[preStart]; int idx search(inorder, inStart, inEnd, root-val); int leftLen idx - inStart; root-left buildTreeHelper(preorder, inorder, preStart 1, preStart leftLen, inStart, idx - 1); root-right buildTreeHelper(preorder, inorder, preStart leftLen 1, preEnd, idx 1, inEnd); return root; } TreeNode* buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) { return buildTreeHelper(preorder, inorder, 0, preorderSize - 1, 0, inorderSize - 1); }这个实现的时间复杂度是 O(n^2)因为每次search都要线性扫描。如果序列很长可以在开始递归前先用哈希表把中序里每个值的下标存下来查找变成 O(1)整体复杂度就能降到 O(n)。LeetCode 105 题就是这么考的。3.3 还原过程的边界条件写这类递归代码最容易出错的是递归传参时的下标计算。我整理几个常见的坑leftLen idx - inStart千万别直接用idx当左子树长度因为inStart不一定是 0递归左子树时前序区间的起点是preStart 1终点是preStart leftLen递归右子树时前序区间的起点是preStart leftLen 1递归出口是preStart preEnd或inStart inEnd两个条件等价写一个就行我在帮学生 debug 这类代码时遇到最多的问题就是下标偏移写错导致重建出来的树形状不对或者直接访问越界。建议你在写完之后手动拿一个小例子走一遍递归流程确认每个区间的数字都对得上再提交代码。4. 遍历能干什么项目里的真实用例4.1 表达式树与编译原理很多人学二叉树遍历时觉得这玩意儿学完就忘好像没什么用。实际上编译器前端解析表达式时用的就是表达式树而表达式树的三种遍历恰好对应三种不同的表达形式。给你一棵表达式树比如 / \ * 5 / \ 3 4前序遍历得到 * 3 4 5这就是前缀表达式波兰式中序遍历得到3 * 4 5这几乎就是我们平时写的算式不过需要注意加括号才能保证优先级后序遍历得到3 4 * 5 这是后缀表达式逆波兰式计算器程序特别喜欢这种形式因为用栈一趟扫完就能求值我自己以前写过一个小的算术表达式求值器就是先把中缀表达式转成后缀表达式再用栈求值。那里面二叉树的后序遍历就是核心环节。如果你之后接触编译原理的语法分析、AST 相关的知识会发现三种遍历根本躲不开。4.2 目录结构、序列化和扁平化再来一个接地气的例子。你的文件系统本质上是一棵多叉树而多叉树可以通过孩子兄弟表示法转换成二叉树。遍历这棵树就是遍历你的目录。前序遍历先打印当前目录再递归进入子目录适合生成目录树结构后序遍历先递归处理完所有子目录再处理当前目录适合做删除操作——你得先把子目录里的文件删光才能删空目录本身这个先子后父的思路在文件操作里特别常见。如果有人要你写一个统计文件夹总大小的函数也是用后序遍历每个目录的大小等于所有子目录文件的大小之和再加上当前目录里直接文件的大小。再比如说二叉树的序列化。你想把一棵二叉树保存到文件里然后下次从文件里恢复它。前序遍历 一个特殊标记符表示空节点就可以做到。这也是为什么 LeetCode 上有一道二叉树序列化与反序列化的题本质上就是让你用好前序遍历。4.3 线索二叉树优化遍历的另类思路热词里出现了线索二叉树这个概念很多教材只在课后题里提一句但如果你要处理大量需要频繁遍历的静态二叉树线索二叉树是一个值得了解的优化手段。普通二叉树的节点里left和right指针不一定都被用到。一个叶子节点的左右指针都是空的白白浪费空间。线索二叉树的想法是让这些空指针指向前驱或后继节点顺便用两个标志位来区分这是正常的子树指针还是线索指针。中序线索二叉树最常用因为中序前驱和后继可以通过线索直接找到遍历时不需要栈、也不需要递归从最左节点开始一路顺着线索往前走就行。typedef struct ThreadNode { int val; struct ThreadNode *left; struct ThreadNode *right; int ltag; // 0 表示 left 指向左孩子1 表示 left 指向前驱 int rtag; // 0 表示 right 指向右孩子1 表示 right 指向后继 } ThreadNode;构建线索的过程就是在中序遍历的同时记录前一个访问的节点pre然后把当前节点的空指针指向pre或pre的空指针指向当前节点。这个代码写起来有点绕但理解了中序遍历的顺序之后逻辑其实很直白。线索二叉树的缺点是结构比普通二叉树复杂插入、删除节点时需要维护线索代价太大。所以它适合建好之后基本不修改只反复遍历的场景。5. 面试与考试中的高频变形题5.1 二叉树的深度和节点统计面试里有个特别常见的问法求二叉树的最大深度。很多不熟悉的人一上来就写层序遍历绕了一大圈其实正确答案就是一句话——用后序遍历的思想递归求左右子树的深度取最大值加一。int maxDepth(TreeNode *root) { if (root NULL) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }这个代码就是后序遍历的变体你先处理完左右子树得到它们的深度再返回当前层的结果。为什么是后序因为只有当你知道左右子树各自的深度时你才能算出当前节点所在子树的深度。这是一个非常典型的由下往上传递结果的思路。类似的还有求节点总数、求叶子节点数、判断两棵树是否相同等题目。只要你能把递归返回什么想清楚这些题本质上都是同一个模板。比如求节点总数就是左子树节点数加右子树节点数再加一。5.2 层级遍历另一种遍历方式严格来说二叉树除了前、中、后序三种深度优先遍历还有一种广度优先遍历也就是层级遍历BFS。它在热词里虽然没被点名但面试题里和它相关的题特别多比如按层打印二叉树、之字形打印、求二叉树的最小深度。层级遍历的实现核心是队列不是栈void levelOrder(TreeNode *root) { if (root NULL) return; TreeNode *queue[1000]; int front 0, rear 0; queue[rear] root; while (front rear) { TreeNode *node queue[front]; printf(%d , node-val); if (node-left) queue[rear] node-left; if (node-right) queue[rear] node-right; } }如果题目要求按层输出也就是每一层单独一个列表那就得在 while 循环里再加一层小循环先记录当前队列的长度然后只处理这一层的节点处理完再进入下一层。这个按层长度切片的技巧很实用很多面试官会顺着这道题继续追问层序遍历的应用比如判断一棵树是不是完全二叉树经典的解法就是用层序遍历遇到空节点之后如果还能再遇到非空节点那它就不是完全二叉树。5.3 判断对称、平衡等衍生考点遍历的思想还能解决很多看起来跟遍历没什么关系的题。举个例子判断一棵二叉树是不是对称的。对称的定义是根节点的左子树和右子树互为镜像。你可以想象成把左子树做一次左右交换然后和右子树比较。递归写法会定义一个新的函数isMirror(left, right)判断时同时向左向右走bool isMirror(TreeNode *left, TreeNode *right) { if (left NULL right NULL) return true; if (left NULL || right NULL) return false; return (left-val right-val) isMirror(left-left, right-right) isMirror(left-right, right-left); }这个递归过程中其实就蕴含了一种同时遍历两棵树的思想。再看判断一棵树是否是平衡二叉树也就是每个节点的左右子树高度差不超过 1做法同样是把后序遍历和求深度结合起来——递归过程中一边计算子树深度一边检查是否平衡如果发现不平衡就直接返回 -1 作为标记。这些变形题看起来各不相同但底层全是对二叉树遍历的理解。掌握好三种基本遍历再理解递归返回值这个灵魂刷题的时候会顺畅很多。6. 实操心得与避坑清单6.1 递归的栈溢出问题写递归遍历时绝大多数教材的示例代码都不会提醒你如果二叉树严重倾斜比如每个节点只有左孩子深度达到几万层时程序会直接崩溃。我自己早年写一个树形结构处理程序时递归遍历一个深度约两万层的树调试了大半天最后发现是栈溢出。后来改成显式栈的迭代写法问题立刻消失。所以如果你要处理的数据量不可控尤其树的形态可能很不平衡建议优先考虑迭代写法。如果非要用递归可以考虑把递归函数改成尾递归形式但 C 语言的尾递归优化并不完全可靠Java 和 Python 更是基本不优化尾递归。最稳妥的方案还是用显式栈。6.2 空指针和边界条件这大概是二叉树代码里最经典的 bug 来源。遍历函数的第一步必须是判断当前节点是否为空然后再访问它的值。但有些同学会在调用递归前判断 孩子不为空才递归结果写出来的代码就变成了条件的多重嵌套逻辑混乱还容易漏掉空节点的情况。另一个常见问题是数组下标的越界。在还原二叉树的题目里递归传参的preStart、preEnd、inStart、inEnd四个下标稍不留神就越界。建议在递归入口处加上断言或者防御性判断调试时能把错误尽早暴露出来。还有指针修改的问题。如果题目要求原地修改二叉树比如把二叉树展开成链表一定要想清楚你是先处理左子树还是先处理右子树处理的顺序不同结果完全不同。我因为在做这类题时没注意指针更新的顺序导致节点丢失白白调试了很久。6.3 我建议的学习路径最后分享一个我个人的学习建议。如果你现在对二叉树遍历还不够熟练不要急着刷大量题目先把一件事做好自己在纸上画一棵树然后手动写出它的前序、中序、后序序列再用代码实现反复验证三遍。这个过程比刷十道题都管用因为它帮你建立了遍历序列和树结构之间的直观映射。数据结构这门课说白了就是逻辑结构 存储结构 基本操作。遍历作为二叉树最基本的操作牵动着后面所有的算法——从求深度、判断平衡到重建二叉树、序列化全都是从这里延伸开来的。我见过很多同学在面试前疯狂刷题但遇到变种题就卡住核心原因就是基础遍历没有内化成自己的直觉。把三种遍历吃透递归和迭代都能默写出来再遇到二叉树相关的问题你会发现大部分题都能在几分钟内找到切入点。后面有时间可以把遍历和二叉搜索树、堆这些进阶话题连起来看知识会成片地串起来。那又是另一篇文章的话题了。