二叉树的遍历和实现几乎是所有写代码的人绕不过去的基本功。不管是大学数据结构课、面试手撕算法还是平时跟树形结构打交道目录树、权限树、语法树、组织架构第一件事永远都是“遍历”。我见过太多类似的场景递归版本能一口气写出来可问到非递归就卡住先序、中序的代码背得滚瓜烂熟但说不清输出为什么是那个顺序更不用说后序遍历十个新手里有三四个会绕进“右子树什么时候访问”的坑里。这篇文章就是想把这套东西讲透遍历顺序是怎么确定的、递归版和非递归版怎么实现、层序怎么按层输出、怎么用遍历序列把树重建回来、二叉树的深度怎么求最后再把我这些年踩过的坑整理成速查表。无论是正在学数据结构还是准备面试或者只是想把底子补扎实这篇都能直接拿来用。1. 先把遍历顺序琢磨透递归序与访问时机1.1 先序、中序、后序到底怎么确定很多人记不住先序、中序、后序是因为在死记“根左右”“左根右”“左右根”这三个口诀。口诀本身没问题但光记住它不够因为一遇到嵌套子树就容易慌。其实可以换个更稳的思路看根节点被访问的时机。对任意一棵二叉树来说“遍历”可以拆成三步访问根节点、遍历左子树、遍历右子树。先序的意思是“先访问根再处理左边最后处理右边”中序是“先处理完左子树再访问根最后处理右边”后序则是“左右子树都处理完了才轮到根”。注意“处理完左子树”不是走到左孩子就结束了而是要把整个左子树的所有节点按同一条规则完整地遍历完才会回到当前节点。这里有一个判断技巧拿到一个节点只看它的左右孩子试着用一条访问顺序描述。比如一个节点叫 A有左孩子 B、右孩子 C先序结果里A 一定在 B、C 前面中序结果里B 在 A 前面A 在 C 前面后序结果里B、C 都在 A 前面。换句话说先序的根在最前后序的根在最后中序的根夹在左右子树之间。这个规律对整棵树成立对每一棵子树也成立所以递归代码才自然。1.2 递归序每个节点其实会被“遇到”三次要说清楚遍历必须先理解一个叫“递归序”的底层模型。随便定义一个递归函数进入函数先处理当前节点然后递归调用左子树再递归调用右子树最后返回。在这个过程里每个节点其实会被经过三次第一次刚进函数还没去左子树第二次左子树处理完刚回来第三次右子树处理完准备返回。如果把打印动作放在不同时机就会得到不同的遍历结果。第一次经过时打印就是先序第二次经过时打印就是中序第三次经过时打印就是后序。我用一个生活化类比帮助记忆你是一个快递员要给每个小区送三趟快递。先序相当于“第一次到门口就把货签收了”中序相当于“第一次去左邻右舍送完回来再签收这一户”后序则是“把左邻右舍和右邻右舍全部送完最后回来签收”。送货路线完全一样只是签收时机不同——返回值顺序自然就不同。理解了这一点以后哪怕忘记口诀只要边画递归树边想“这是第几次经过”就能把顺序推出来。2. 节点定义与递归版遍历教科书打底2.1 先把树的节点定义好实现之前先把数据结构设计好。这里我统一用 C# 写示例换成 Java、C思路是一样的差别只在一个语法外壳。public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val 0, TreeNode left null, TreeNode right null) { this.val val; this.left left; this.right right; } }这个类很简单一个值域加左右孩子引用。工程里树节点往往还会加 parent 指针、节点高度、子树大小等字段但做遍历练习时不必过早引入保持结构最小反而更容易看清算法本质。2.2 递归遍历三行代码背后的调用栈递归版遍历的代码非常短短到很多人背下来就以为自己会了。还是建议看一眼就好重点理解函数是怎么一层层展开、又一层层收回的。public void Preorder(TreeNode root) { if (root null) return; Console.Write(root.val ); Preorder(root.left); Preorder(root.right); } public void Inorder(TreeNode root) { if (root null) return; Inorder(root.left); Console.Write(root.val ); Inorder(root.right); } public void Postorder(TreeNode root) { if (root null) return; Postorder(root.left); Postorder(root.right); Console.Write(root.val ); }三个函数的唯一区别就是打印语句的位置。为什么一个 base caseroot null就够了因为递归的每一步都在缩小问题规模走到空节点就说明没东西可处理了直接返回回到上一层节点继续执行。用调用栈来看每次调用Preorder(root.left)时当前函数的局部状态会压进系统栈等左子树处理完再从栈顶弹出恢复现场接着执行Preorder(root.right)。这就是为什么递归代码天然具备“回溯”能力。时间复杂度很清晰每个节点恰好被访问一次所以是 O(n)空间复杂度取决于树高理想情况下是 O(log n)如果树退化成一个链表就会变成 O(n)这也是后面为什么需要非递归的现实原因。2.3 用一个例子把三种结果跑明白代码有了但纸上谈兵容易错。手动推演一棵具体的树比看一百行注释都有用。假设有这么一棵二叉树1 / \ 2 3 / \ / \ 4 5 6 7递归走一遍先序从 1 开始打印 1进左子树打印 2进 2 的左子树打印 4回到 2进右子树打印 5回到 1进右子树打印 3继续 6、7。结果是1 2 4 5 3 6 7。中序先不打印根先把 1 的左子树完整跑完。1 的左子树里4 的左右为空所以先打印 4回到 2 时打印 2再走 2 的右子树打印 5整个左子树结束回到 1 打印 1然后处理右子树3 的左孩子 6 先打印再打印 3最后打印 7。结果是4 2 5 1 6 3 7。后序先去左子树4 和 5 都处理完才轮到 2去右子树6 和 7 都处理完才轮到 3最后才是根 1。结果是4 5 2 6 7 3 1。建议自己拿纸画一遍。画的时候在每个节点旁边标三个点分别代表“刚进来”“左子树回来”“右子树回来”打印对应点的顺序就是遍历结果。这个训练熟练以后看任何递归遍历代码都会像看剧本一样一目了然。3. 非递归实现的完整套路从手工栈到层序队列3.1 为什么不用递归工程风险和思维锻炼既然递归版这么简洁为什么还要学非递归第一个原因是工程风险递归深度等于树高。如果二叉树退化成一条链一万层节点的树就可能触发栈溢出。系统栈不像堆内存那样方便扩容线上出现这种问题非常难排查。第二个原因是思维锻炼非递归强制你用显式的栈或队列重现“系统帮你做的事”这个能力在做回溯算法、表达式求值、编译器语法分析时都会复用。第三个原因是面试考核很多面试官会顺着递归版追问一句“如果树特别深呢”能写出非递归就是加分项。栈和递归的关系可以理解成同一个算法的两种表达方式。递归时系统栈自动帮你记录每一层该回到哪个节点非递归时你得自己把“下一个要处理的节点”压进栈里等时机到了再弹出来。3.2 先序和中序的统一迭代模板先序遍历的非递归写法很直接。核心思路是模拟“从根出发一路向左走边走边打印走到头再回头处理右边”的过程。public IListint PreorderTraversal(TreeNode root) { var result new Listint(); var stack new StackTreeNode(); var cur root; while (cur ! null || stack.Count 0) { while (cur ! null) { result.Add(cur.val); // 第一次经过就访问对应先序 stack.Push(cur); cur cur.left; } cur stack.Pop(); cur cur.right; } return result; }先序代码为什么先打印再压栈因为我们希望“一碰到节点就记录”然后赶紧往左走等到左边全走完才轮到右边。栈里保存的是“欠着的父节点”等左子树到头了一个个弹出来补走右子树。中序和先序只差一行把打印动作从“压栈前”挪到“弹栈后”public IListint InorderTraversal(TreeNode root) { var result new Listint(); var stack new StackTreeNode(); var cur root; while (cur ! null || stack.Count 0) { while (cur ! null) { stack.Push(cur); cur cur.left; } cur stack.Pop(); result.Add(cur.val); // 左子树处理完、回到当前节点时再访问 cur cur.right; } return result; }用示例树验证一下先不断压入 1、2、4走到 4 的左孩子为空弹出 4 打印再去看 4 的右孩子右孩子为空回到外层循环继续弹出 2 打印……最终得到4 2 5 1 6 3 7。这套模板理解后先序中序就都在手里了只需要记“先序在压栈前打印中序在弹栈后打印”。3.3 后序非递归反转法是最容易上手的解法后序的非递归比先序、中序都麻烦原因在于后序要求“第三次经过节点才访问”可迭代写法中节点从栈里弹出来时很难一眼判断这是从左子树返回的还是从右子树返回的。如果是左子树返回的还不能访问得先拐去右子树。最容易理解的解法是“反转法”。核心思想后序是“左、右、根”如果我做一次“根、右、左”的遍历再把结果整体反转不就变成“左、右、根”了吗public IListint PostorderTraversal(TreeNode root) { var result new Listint(); var stack new StackTreeNode(); if (root null) return result; stack.Push(root); while (stack.Count 0) { var node stack.Pop(); result.Add(node.val); if (node.left ! null) stack.Push(node.left); if (node.right ! null) stack.Push(node.right); } result.Reverse(); return result; }很多人第一次看到这段代码会懵先压左孩子再压右孩子弹出来不是该先处理右孩子吗输出结果顺序是什么推一遍就明白了栈是后进先出先压左后压右弹出顺序是“右孩子先于左孩子”所以结果顺序是“根、右、左”最后Reverse()一下得到“左、右、根”。这段代码虽然不直接模拟传统后序的访问轨迹但它结果正确也很好记作为日常实现和面试手写足够用。如果想要一次遍历直接得到后序结果、不依赖 Reverse可以使用“标记位”方案栈里压入节点时同时压入一个布尔值false 表示还没处理过true 表示第二次遇到、可以访问。也可以用变量记录上一次访问的节点。下面是单栈加上次访问节点的写法public IListint PostorderTraversal(TreeNode root) { var result new Listint(); var stack new StackTreeNode(); TreeNode cur root; TreeNode lastVisited null; while (cur ! null || stack.Count 0) { while (cur ! null) { stack.Push(cur); cur cur.left; } var peekNode stack.Peek(); if (peekNode.right ! null lastVisited ! peekNode.right) { cur peekNode.right; } else { result.Add(peekNode.val); lastVisited peekNode; stack.Pop(); } } return result; }这个版本的判断逻辑值得反复读当前节点右孩子存在且上一个访问的节点不是它的右孩子说明右子树还没遍历于是先拐去右孩子如果右孩子为空或者右孩子刚刚被访问完就说明左右子树都已经处理完毕此时才轮到当前节点本身。用lastVisited区分“从左边回来”还是“从右边回来”正是后序迭代的钥匙。3.4 层序遍历与按层输出的队列实现先序、中序、后序是深度优先遍历DFS层序遍历则是广度优先遍历BFS。它不再依赖栈而是用队列逐层扫描先把根入队每次从队头取出一个节点把它的左右孩子依次放入队尾直到队列为空。public IListIListint LevelOrder(TreeNode root) { var result new ListIListint(); if (root null) return result; var queue new QueueTreeNode(); queue.Enqueue(root); while (queue.Count 0) { int levelSize queue.Count; var level new Listint(); for (int i 0; i levelSize; i) { var node queue.Dequeue(); level.Add(node.val); if (node.left ! null) queue.Enqueue(node.left); if (node.right ! null) queue.Enqueue(node.right); } result.Add(level); } return result; }有个关键细节为什么循环里要先记录levelSize queue.Count而不是直接用queue.Count作为循环条件因为Dequeue过程中队列长度会变化而且新入队的下一层节点会混进来。只有在循环开始前固定住“这一层原本有多少个节点”才能恰好在循环结束位置得到这一层的完整结果同时队列里只剩下一层节点。示例树按层输出的结果是[ [1], [2, 3], [4, 5, 6, 7] ]。层序遍历非常适合解决“二叉树最大宽度”“右视图”“每层最大值”这类问题因为按层输出本身就把层的信息保留下来了。宽度优先的算法步骤可以浓缩成四步初始化队列根节点入队记录当前层节点数循环取出当前层节点并记录把每个节点的左右孩子入队进入下一层。4. 由遍历序列重建二叉树与深度计算从会写到会用4.1 只知道一种遍历序列够不够先问一个很实际的问题给定一个先序序列能唯一确定一棵二叉树吗答案是不能。比如先序序列[1, 2]根是 1但 2 可能是 1 的左孩子也可能是右孩子两种树的先序结果都是[1, 2]。后序序列同理。层序更不必说同样的层序结果可能对应很多种结构。所以“由遍历序列重建二叉树”至少需要两种序列而且通常要有中序。原因在于前序或后序能帮我们定位根节点但分不清左右子树的边界中序则能利用根节点把剩余部分切成左子树和右子树两块。给一棵树先序遍历第一个元素一定是根在中序里找到这个根的下标左边就是左子树的中序右边就是右子树的中序再利用左右子树的长度回到先序里切出对应的左、右子树先序递归往下做。这个思路正是 4.2 的代码基础。那“先序 后序”行不行绝大多数情况下不行因为当节点只有一棵子树时先序和后序都无法判断这个孩子到底在左边还是右边树形就不唯一。这个考点在面试里出现频率不低值得在心里多过几遍。4.2 先序 中序重建二叉树的实现重建树的递归版代码不长难在边界索引计算。我建议用“左子树长度”来推边界而不是硬记左端点和右端点能省掉一大批 off-by-one 错误。public TreeNode BuildTree(int[] preorder, int[] inorder) { return Build(preorder, 0, preorder.Length - 1, inorder, 0, inorder.Length - 1); } private TreeNode Build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart preEnd || inStart inEnd) return null; int rootVal preorder[preStart]; var root new TreeNode(rootVal); int mid inStart; while (inorder[mid] ! rootVal) mid; int leftSize mid - inStart; root.left Build(preorder, preStart 1, preStart leftSize, inorder, inStart, mid - 1); root.right Build(preorder, preStart leftSize 1, preEnd, inorder, mid 1, inEnd); return root; }这里每一轮先取preorder[preStart]作为根的值再到中序区间[inStart, inEnd]里找出根的位置mid。中序里从inStart到mid - 1的就是左子树所有节点数量为leftSize。那么在先序里左子树范围从preStart 1开始连续leftSize个所以到preStart leftSize结束剩余部分从preStart leftSize 1往后属于右子树。每次用线性查找找根在中序里的位置总时间复杂度是 O(n²)。如果想优化到 O(n)可以预先把中序所有值对应的下标存进字典之后每次按值查找就是 O(1)。代码上的改动也直观在递归前遍历一次 inorder建立一个Dictionaryint, int递归时用map[rootVal]拿到 mid其他逻辑不用动。很多大型树重建场景下这个优化能明显减少耗时。4.3 二叉树的深度怎么求递归与层序两条路“二叉树的深度”在很多刷题平台上也叫“二叉树的最大深度”定义是从根节点到最远叶子节点的最长路径上的节点数。最小规模的子树是空树深度为 0这是递归最容易想到的出口。递归实现非常短public int MaxDepth(TreeNode root) { if (root null) return 0; return 1 Math.Max(MaxDepth(root.left), MaxDepth(root.right)); }理解这句代码的关键是自底向上每个节点先问左子树“你有多深”再问右子树“你有多深”取较大的那个加一就是当前节点为根的树的最大深度。示例树里节点 4、5、6、7 的深度都是 1节点 2 左右子树深度都是 1所以自身深度是 2节点 3 同理是 2根 1 取左右子树较大深度 2加一得到整棵树深度 3。很多人只写递归忘了层序遍历也能求深度。层序遍历每处理完一层深度加一当队列清空时累计的层数就是最大深度。相比递归层序版本不需要考虑递归栈深度二叉树特别深时反而更稳。手动推演时也可以把“层数”直接数出来根一层2、3 一层4、5、6、7 一层一共 3 层。5. 实际踩坑记录常见问题与排查思路5.1 最常见问题速查表下面这些问题是带新人和自己刷题时反复遇到的直接整理成速查表更实用。现象根因与解法空树报空引用异常递归版漏写root null的出口迭代版在访问root.val前没有判空。先处理空树再走主逻辑先序/中序顺序颠倒总差一步打印位置放错。先序在压栈前打印中序在弹栈后打印后序在处理完右子树后打印非递归代码死循环最常见原因是 cur 没有“向右转”。弹出节点后要记得执行cur cur.right否则会反复处理同一个左子树后序单栈法输出不对没记录 lastVisited。必须判断“右孩子已经访问过”或“右孩子为空”两个条件才能访问当前节点层序遍历想按层输出却混在一起while 循环里直接拿queue.Count当每层长度。要在取每层前先固定levelSize queue.Count重建树时数组越界根在中序的位置搜索区间错了。要先限定在[inStart, inEnd]范围内查找并且用 leftSize 来切分前序区间运行结果整体相反后序先压左再压右再用 Reverse 反转层序没有从队尾入队。把入栈入队顺序画出来检查一遍5.2 排查方法画图、打桩、小用例验证我自己排查遍历问题时有一个几十年不变的习惯先拿一张纸画一棵三层左右的普通树把每个节点旁边标上递归序的三个经过点再手动写出期望的遍历结果最后写代码对照。这个做法听起来慢实际能省下大量调试时间。还有个特别有用的自查手段是针对二叉搜索树的性质对一棵二叉搜索树做中序遍历结果必然是严格递增的。如果我实现的中序遍历结果不是递增序列不用猜一定是“访问根的时机”放错了。反向也成立可以通过打印中序结果来验证手写的树结构对不对。打桩调试时不要只打印最终结果最好在关键位置打印当前节点值、当前栈顶节点值、当前访问时机方便观察执行轨迹。5.3 顺手补充的边界用例写遍历算法边界用例最好标准化不要每次临时想。建议准备这么几个测试场景空树、只有一个节点的树、只有左子树的链式树、只有右子树的链式树、左右子树都存在的普通树。只测普通树会掩盖许多边界 bug。比如只有右子树的链式结构很多先序中序代码都能跑但后序反转法如果压栈顺序没想明白输出很可能和预期差一个身位。链式结构还直接暴露递归深度问题结构稍微长一点递归版本立刻性能变差。我之前在线上一段数据补全逻辑里见过一个递归遍历目录树的写法目录深层嵌套两百多层时直接抛了StackOverflowException后来改成显式栈迭代才恢复稳定。这个案例说明不是所有地方都适合写递归写之前先评估最坏深度是工程里最实用的习惯之一。6. 写在最后我的一点实战体会聊了这么多最后一个建议可能比前面所有代码都重要别背模板背“访问时机”。我每次带新人第一件事都是让他拿笔在纸上画一棵树标出每个节点的三次经过点然后自己把先序、中序、后序结果推出来能推出来代码怎么写只是顺水推舟的事。因为模板可以忘但“先序是第一次经过时打印中序是第二次后序是第三次”这条主线几乎不可能忘。另一个亲身经历是调试遍历代码时最实用的工具不是高级调试器而是在关键路径上插几行打印把“当前节点”“当前栈顶”“刚访问过的节点”一起打出来。很多人写后序失败就是因为看不到lastVisited到底有没有更新。把状态打出来看一眼往往一眼就能发现问题所在。如果你刚开始学也别急着把递归版和非递归版全记下来。先写递归版跑通示例树再对照递归版一行行改非递归版脑子里始终存着“递归调用栈长什么样”的画面自然水到渠成。等这四种遍历都写熟了再去碰线索二叉树、AVL 树、树的序列化与反序列化这些进阶内容会发现基础越扎实进阶越轻松。