提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录前言一、先序遍历1. 递归实现 (Recursive)2. 迭代实现 (Iterative)小结与思考二、中序遍历1. 递归实现 (Recursive)2. 迭代实现 (Iterative) 深度对比三、后序遍历1. 递归实现 (Recursive)2. 迭代实现 (Iterative) —— 双栈法 核心难点四、层序遍历1. 核心实现Java2. 进阶版分层输出 为什么层序遍历不用递归五、二叉树还原1. 各大遍历结果的“线索”特点2. 破案实例先序 中序推导步骤3. 为什么一定要中序总结前言在数据结构的面试与实战中二叉树Binary Tree 永远是绕不开的核心。它既不像数组、链表那样线性直观也不像图论那样错综复杂它是许多高级算法如堆排序、平衡树、红黑树的基石。理解二叉树最基本的功法就是遍历。很多人能熟练写出递归版本但在面对迭代非递归实现或是“如何根据遍历结果还原一棵树”时往往会感到逻辑模糊。本篇博客将带你深度剖析深度优先搜索DFS前序、中序、后序的三种递归与迭代实现。广度优先搜索BFS层序遍历的优雅实现。逻辑逆推如何利用遍历序列间的物理联系完美还原出一棵二叉树。无论你是为了面试冲刺还是为了夯实算法基础希望这篇文章能帮你彻底打通二叉树的“任督二脉”。一、先序遍历先序遍历Preorder Traversal的特点是根节点 - 左子树 - 右子树。在处理逻辑上它是最符合直觉的因为我们一碰到节点就立刻对其进行操作。我们可以通过递归和迭代非递归两种方式来实现。1. 递归实现 (Recursive)这是最简洁的方式利用系统栈自动保存状态。publicvoidpreOrderRecursive(TreeNoderoot){if(rootnull){return;}// 1. 访问根节点System.out.print(root.val );// 2. 递归遍历左子树preOrderRecursive(root.left);// 3. 递归遍历右子树preOrderRecursive(root.right);}2. 迭代实现 (Iterative)面试官通常更喜欢考察迭代写法因为它能展示你对**栈Stack**结构的理解。核心逻辑利用栈“后进先出”的特性。为了保证左子树先被访问我们需要先将右孩子压栈再将左孩子压栈。publicvoidpreOrderIterative(TreeNoderoot){if(rootnull){return;}StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();// 访问当前节点System.out.print(node.val );// 关键先压右孩子再压左孩子if(node.right!null){stack.push(node.right);}if(node.left!null){stack.push(node.left);}}}小结与思考特点先序遍历常用于复制一棵树或者计算前缀表达式。在迭代法中栈顶元素始终是我们下一步要处理的“局部根节点”。二、中序遍历中序遍历Inorder Traversal的顺序是左子树 - 根节点 - 右子树。在二叉搜索树BST中中序遍历的结果恰好是升序排列的这也是它最著名的特性。1. 递归实现 (Recursive)递归逻辑非常丝滑只需改变访问根节点的时机publicvoidinOrderRecursive(TreeNoderoot){if(rootnull){return;}// 1. 递归遍历左子树inOrderRecursive(root.left);// 2. 访问根节点System.out.print(root.val );// 3. 递归遍历右子树inOrderRecursive(root.right);}2. 迭代实现 (Iterative)中序遍历的迭代比先序稍微复杂一点。因为我们要“一头扎到底”找到最左侧的节点然后再回头处理根节点。核心逻辑使用指针一路向左压栈直到尽头弹出栈顶元素并访问然后转向该节点的右子树重复此过程。publicvoidinOrderIterative(TreeNoderoot){if(rootnull){return;}StackTreeNodestacknewStack();TreeNodecurrroot;while(curr!null||!stack.isEmpty()){// 1. 尽可能向左走将路径上的节点全部压栈while(curr!null){stack.push(curr);currcurr.left;}// 2. 弹出并访问最左侧节点或局部根节点currstack.pop();System.out.print(curr.val );// 3. 转向右子树currcurr.right;}} 深度对比先序迭代进栈时就访问逻辑更像“走马观花”。中序迭代出栈时才访问逻辑更像“深度摸排”必须先确保左边没人了才轮到自己。三、后序遍历后序遍历Postorder Traversal的顺序是左子树 - 右子树 - 根节点。它是四种遍历中逻辑最“隐忍”的必须等左右子树全部处理完最后才轮到根节点。这使得它在计算文件夹大小或销毁二叉树先删子节点再删父节点时非常有用。1. 递归实现 (Recursive)依然是最符合直觉的写法只需将访问操作放在两次递归之后publicvoidpostOrderRecursive(TreeNoderoot){if(rootnull){return;}// 1. 递归遍历左子树postOrderRecursive(root.left);// 2. 递归遍历右子树postOrderRecursive(root.right);// 3. 最后访问根节点System.out.print(root.val );}2. 迭代实现 (Iterative) —— 双栈法后序遍历的迭代是公认的难点因为根节点要“二进宫”经过它去左边回来经过它去右边最后才能处理它。巧妙思路先序遍历是根 - 左 - 右。如果我们稍微修改成根 - 右 - 左得到的结果序列再反转一下不就变成了左 - 右 - 根即后序吗publicvoidpostOrderIterative(TreeNoderoot){if(rootnull)return;StackTreeNodes1newStack();StackTreeNodes2newStack();// 辅助栈用于反转结果s1.push(root);while(!s1.isEmpty()){TreeNodenodes1.pop();s2.push(node);// 进s2相当于暂存最后统一弹出就实现了反转// 注意这里先左后右弹出时就是先右后左if(node.left!null)s1.push(node.left);if(node.right!null)s1.push(node.right);}// 统一打印 s2 中的元素while(!s2.isEmpty()){System.out.print(s2.pop().val );}} 核心难点后序遍历的迭代如果不使用双栈就需要维护一个lastVisited指针来判断右子树是否已经处理完逻辑会复杂很多。双栈法是面试中最推荐的“曲线救国”方案代码极其整洁。四、层序遍历层序遍历Level Order Traversal属于广度优先搜索BFS。它的规则非常直观按层从上到下每层从左到右依次访问。与前三种遍历使用“栈”不同层序遍历的核心武器是队列Queue利用它“先进先出”的特性来保证访问顺序。1. 核心实现Java在 Java 中我们通常使用LinkedList或ArrayDeque来实现Queue接口。publicvoidlevelOrder(TreeNoderoot){if(rootnull){return;}// 使用队列存储待访问节点QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){// 弹出队头节点TreeNodenodequeue.poll();System.out.print(node.val );// 按照从左到右的顺序将子节点入队if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}}2. 进阶版分层输出在实际面试中经常要求你按层输出比如返回ListListInteger这时我们需要在while循环内部记录当前层的节点数量。publicListListIntegerlevelOrderGroups(TreeNoderoot){ListListIntegerresultnewArrayList();if(rootnull)returnresult;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intlevelSizequeue.size();// 当前层的节点个数ListIntegercurrentLevelnewArrayList();for(inti0;ilevelSize;i){TreeNodenodequeue.poll();currentLevel.add(node.val);if(node.left!null)queue.offer(node.left);if(node.right!null)queue.offer(node.right);}result.add(currentLevel);// 将整层结果加入大列表}returnresult;} 为什么层序遍历不用递归虽然层序遍历也可以用递归实现通过传入深度depth参数但那本质上是 DFS 的变体且逻辑不如队列实现直观。队列法才是 BFS 的灵魂所在。五、二叉树还原要还原一棵二叉树仅靠一种遍历是不够的除非是带空节点的先序。我们通常需要“深度优先”中的两种组合且其中必须包含中序遍历。1. 各大遍历结果的“线索”特点遍历方式结果序列的物理特征核心作用先序 (Preorder)[根节点, [左子树], [右子树]]找根第一个元素永远是当前的根。中序 (Inorder)[[左子树], 根节点, [右子树]]定边界一旦确定根节点左边全是左子树右边全是右子树。后序 (Postorder)[[左子树], [右子树], 根节点]找根最后一个元素永远是当前的根。2. 破案实例先序 中序假设我们有以下两组序列先序 (Preorder):[A, B, D, E, C, F]中序 (Inorder):[D, B, E, A, C, F]推导步骤第一步找根看先序第一个字母是A。说明A是整棵树的根。第二步切分在中序中找到A。A左边是[D, B, E]这 3 个就是A 的左子树。A右边是[C, F]这 2 个就是A 的右子树。第三步递归在先序中扣掉 A接下来的 3 个[B, D, E]是左子树的先序。重复第一步左子树先序第一个是B说明B是 A 的左孩子。在中序[D, B, E]中看B左边是 D右边是 E。最终形态A 是总根左连 B右连 C。B 的左是 D右是 E。C 的右是 F因为中序里 C 在 F 左边。3. 为什么一定要中序如果没有中序只有先序[A, B]和后序[B, A]我们无法确定 B 是 A 的左孩子还是右孩子。中序遍历通过“根节点在中间”的特性提供了唯一的左右空间定位。总结推荐大家自己画图推导一下二叉树的遍历过程以及二叉树的还原过程画图做一遍就能有很深的理解大家都动手试试吧