1. 遍历不是背代码而是理解二叉树的“访问顺序”很多人第一次接触二叉树遍历都是从背递归模板开始的。先序就是“根左右”中序就是“左根右”后序就是“左右根”层序就是一层一层来。背完之后写个Demo能跑通但一旦遇到非递归实现、Morris遍历、或者面试官追问“为什么中序能还原二叉搜索树”立刻就卡住了。我见过太多这样的情况面试时让手写一个非递归后序遍历候选人憋了半天写出一个用两个栈的版本问他为什么用两个栈答不上来。再问能不能用一个栈实现直接摇头。其实这些问题的答案都藏在“遍历的本质”里——遍历就是按照某种规则把树上的每个节点访问一次且仅一次。不同的规则对应不同的访问顺序而不同的实现方式只是在用不同的工具模拟这个访问过程。这篇文章会从最基础的递归开始逐步展开到非递归、Morris、层序的多种实现方式覆盖先序、中序、后序、层序四种遍历。每种方法我都会解释清楚它的核心思路、适用场景、以及实际写代码时容易踩的坑。无论你是正在准备面试还是想彻底搞懂二叉树遍历的底层逻辑这篇文章都能给你一个清晰的路线图。先说一下整体思路。二叉树的遍历实现大致可以分为几个层次递归是最直观的代码简洁但受限于调用栈深度非递归用显式栈来模拟递归过程可控性更强Morris遍历利用叶子节点的空指针建立临时线索把空间复杂度降到O(1)层序遍历则需要借助队列按层访问。每种方法都有它的价值和适用场景不是越复杂越好而是要看具体需求。2. 递归实现最直观但也最容易忽略细节的方案2.1 递归遍历的代码结构与调用栈分析递归实现二叉树遍历代码确实简洁到令人发指。先序就是先访问当前节点再递归左子树再递归右子树。中序就是把访问操作放到中间后序放到最后。三行代码的差别对应三种完全不同的访问顺序。但简洁不代表简单。很多人写递归遍历时对调用栈的变化过程是没有概念的。我建议你在初学阶段拿一棵只有七个节点的满二叉树手动画出递归调用的完整过程。以先序遍历为例根节点先被访问然后一路向左走到最深处每到一个节点就先记录左子树走完了再回头走右子树。这个“回头”的过程就是函数调用栈在起作用。调用栈的深度直接决定了递归方案的空间复杂度。对于一棵退化成链表的二叉树递归深度就是节点数n空间复杂度是O(n)。在大多数现代编程语言中默认的栈空间是有限的如果树的深度过大就会触发栈溢出错误。这不是理论上的担忧我在实际项目中就遇到过——处理一棵深度超过一万的树时递归直接崩了换成非递归才解决问题。所以递归方案适合什么场景树的结构比较平衡、深度可控、代码可读性优先的场景。比如解析表达式树、构建语法树这类应用递归写起来清晰明了维护成本低。但如果树的深度不可控或者运行环境栈空间受限就必须考虑非递归方案。2.2 三种递归顺序的相互转换技巧先序、中序、后序的递归代码结构几乎一样区别只在于访问根节点的时机。先序在进入左右子树之前访问中序在左子树返回之后、右子树之前访问后序在左右子树都返回之后访问。这里有一个很实用的技巧如果你能写出先序遍历的递归代码把访问操作移到递归调用之间就是中序移到之后就是后序。这个转换规律看起来简单但很多人第一次接触时容易搞混。我的建议是不要死记而是理解“访问时机”和“子树处理进度”之间的关系。还有一个常见的面试题如何只用先序和中序的递归框架写出后序遍历答案是利用一个辅助栈按照“根右左”的顺序先序遍历把结果依次压栈最后弹出就是“左右根”。这个技巧在非递归实现中也会用到后面会详细展开。递归方案还有一个容易忽略的细节访问操作具体做什么。在遍历框架中“访问”通常是一个抽象操作可以是打印节点值、收集到列表、修改节点属性等。在实际项目中遍历往往不是目的而是手段。比如你要在遍历过程中累加某个值、查找特定节点、或者构建新的数据结构。这时候递归函数的返回值设计就很重要了。如果只是打印返回void就够了如果需要传递状态可能需要返回一个值或者使用全局变量。2.3 递归方案的性能瓶颈与栈溢出风险递归方案最大的问题就是栈空间。每次递归调用都会在调用栈上创建一个新的栈帧保存参数、局部变量和返回地址。对于深度为h的二叉树递归遍历的空间复杂度是O(h)。在平衡二叉树中h约等于log n问题不大但在最坏情况下h等于n空间复杂度退化为O(n)。栈溢出不是闹着玩的。我在一个数据处理项目中需要遍历一棵由用户输入构建的二叉树。正常情况下树的深度不会超过几十层但有一次用户输入了一个极端不平衡的结构深度直接飙到几万层递归遍历当场崩溃。后来改成非递归实现问题才解决。除了栈溢出递归还有函数调用开销。每次调用都有压栈、跳转、返回的过程虽然现代编译器会做一些优化但在性能敏感的场景下递归的开销仍然不可忽视。如果你需要遍历一棵非常大的树而且对性能有要求非递归方案通常是更好的选择。不过话说回来递归方案的可读性和可维护性是最好的。在大多数业务场景中树的深度不会太大递归完全够用。我的建议是先用递归实现如果遇到性能问题或栈溢出再考虑改成非递归。不要为了追求“高级”而过度设计。3. 非递归实现用栈模拟递归的完整拆解3.1 先序非递归为什么用栈以及入栈顺序的讲究先序遍历的非递归实现核心思路是用一个栈来模拟递归调用栈。递归是先访问根节点然后递归左子树再递归右子树。对应到栈操作就是弹出栈顶节点并访问然后先把右子节点入栈再把左子节点入栈。这样下次弹出栈顶时就会先处理左子节点符合先序的顺序。这里有一个关键细节入栈顺序必须是“先右后左”。因为栈是后进先出如果先入左再入右弹出时就会先处理右子节点变成“根右左”的顺序。这个细节看起来简单但我在面试中见过不少人写反了导致遍历结果完全错误。先序非递归的代码框架大概是这样的def preorder(root): if not root: 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这段代码的时间复杂度是O(n)每个节点入栈出栈各一次。空间复杂度是O(h)h是树的高度因为栈中最多同时保存从根到某个叶子路径上的节点。有一个变体是先序非递归的另一种写法用一个指针cur从根节点开始一路向左走沿途访问节点并把右子节点入栈。这种写法在Morris遍历中会用到类似的思想后面会详细讲。3.2 中序非递归一路向左再回头的逻辑中序遍历的非递归实现比先序稍微复杂一点因为访问根节点的时机是在左子树处理完之后。核心思路是从当前节点出发一路向左走沿途把节点压入栈直到没有左子节点为止。然后弹出栈顶节点并访问再把当前指针指向该节点的右子节点重复上述过程。这个过程的逻辑是栈中保存的是“已经走过左子树但还没访问”的节点。每次弹出栈顶就意味着该节点的左子树已经全部处理完了现在可以访问该节点然后转向右子树。def inorder(root): stack [] result [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result这段代码的关键在于理解两个循环的配合。外层循环的条件是“当前节点不为空或者栈不为空”内层循环负责一路向左。当内层循环结束时栈顶就是最左下的节点弹出并访问然后转向右子树。中序非递归在实际中有一个非常重要的应用验证二叉搜索树。二叉搜索树的中序遍历结果是有序的所以只需要在中序遍历过程中检查当前节点值是否大于前一个节点值即可。这个思路比递归验证更直观也更容易处理边界情况。3.3 后序非递归最难的遍历顺序与两种经典解法后序遍历的非递归实现是三种深度优先遍历中最难的因为访问根节点的时机是在左右子树都处理完之后。这意味着我们需要知道“右子树是否已经处理完”这个信息。第一种经典解法是用两个栈。第一个栈按照“根右左”的顺序进行类似先序的遍历把访问结果依次压入第二个栈。由于“根右左”的逆序就是“左右根”所以第二个栈的弹出顺序就是后序遍历的结果。def postorder_two_stacks(root): if not root: return [] stack1 [root] stack2 [] while stack1: node stack1.pop() stack2.append(node) if node.left: stack1.append(node.left) if node.right: stack1.append(node.right) result [] while stack2: result.append(stack2.pop().val) return result第二种解法是用一个栈加一个指针记录上一次访问的节点。核心逻辑是对于栈顶节点如果它的右子节点为空或者右子节点就是上一次访问的节点说明右子树已经处理完了可以访问当前节点。否则需要先处理右子树。def postorder_one_stack(root): if not root: return [] stack [root] result [] last_visited None while stack: node stack[-1] if (not node.left and not node.right) or (last_visited and (last_visited node.left or last_visited node.right)): result.append(node.val) stack.pop() last_visited node else: if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result这两种解法各有优劣。两个栈的版本代码更简洁容易理解和记忆但空间复杂度是O(n)因为需要额外的栈来保存所有节点。一个栈加指针的版本空间复杂度是O(h)更节省空间但逻辑更复杂容易写错。我在实际使用中的体会是如果只是面试或者临时用一下两个栈的版本足够了不容易出错。如果是在生产环境中处理大规模数据一个栈的版本更合适但一定要仔细测试边界情况特别是只有一个子节点的节点和叶子节点。3.4 非递归方案的统一框架与常见错误三种非递归遍历虽然写法不同但本质上都是在用栈模拟递归。先序和中序的代码结构比较接近后序需要额外处理“右子树是否已访问”的问题。常见的错误包括先序入栈顺序写反、中序忘记处理右子树、后序判断条件不完整。还有一个容易忽略的点是空节点的处理。在递归方案中空节点直接返回不需要额外判断。但在非递归方案中入栈前必须检查子节点是否为空否则会把空节点压入栈导致后续操作出错。另一个常见问题是对“访问”操作的理解。在非递归代码中“访问”通常发生在弹出栈顶的时候。但后序的一个栈版本中“访问”发生在判断条件满足时而不是弹出时。这个区别需要特别注意。如果你想让代码更通用可以写一个统一的非递归遍历框架通过一个标志位来控制访问时机。但这种写法可读性会下降实际项目中不太推荐。我的建议是三种遍历分别写代码清晰比“优雅”更重要。4. Morris遍历把空间复杂度压到O(1)的巧妙思路4.1 Morris遍历的核心思想利用叶子节点的空指针Morris遍历是一个很巧妙的算法它利用二叉树中大量存在的空指针来建立临时线索从而在不需要栈的情况下完成遍历。核心思想是对于当前节点如果它有左子树就找到左子树中最右的节点即左子树的中序前驱把这个节点的右指针指向当前节点。这样在遍历完左子树后就能通过这个临时指针回到当前节点。这个过程说起来有点绕但画个图就清楚了。假设有一棵简单的树根节点是1左子节点是2右子节点是3。对于节点1它的左子树是以2为根的子树最右节点就是2本身。把2的右指针指向1然后进入左子树。处理完左子树后通过2的右指针回到1此时左子树已经处理完可以访问1然后进入右子树。Morris遍历的关键在于建立临时线索和拆除临时线索。建立线索是为了能够回到当前节点拆除线索是为了恢复树的原始结构。如果不拆除树的结构就被破坏了后续操作会出错。4.2 Morris先序与中序线索建立与拆除的时机Morris中序遍历的代码框架如下def morris_inorder(root): result [] cur root while cur: if not cur.left: result.append(cur.val) cur cur.right else: predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right if not predecessor.right: predecessor.right cur cur cur.left else: predecessor.right None result.append(cur.val) cur cur.right return result这段代码的逻辑是如果当前节点没有左子树直接访问并转向右子树。如果有左子树找到左子树的最右节点。如果最右节点的右指针为空说明是第一次访问当前节点建立线索并进入左子树。如果最右节点的右指针指向当前节点说明左子树已经处理完拆除线索访问当前节点然后转向右子树。Morris先序遍历和中序的区别在于访问时机。中序是在拆除线索后访问当前节点先序是在建立线索前访问当前节点。这个区别很小但结果完全不同。Morris遍历的时间复杂度是O(n)因为每条边最多被访问两次。空间复杂度是O(1)不需要额外的栈或队列。这个优势在处理大规模数据时非常明显。4.3 Morris后序最复杂的变体与实现技巧Morris后序遍历是三种中最复杂的。核心思路是对于当前节点先处理左子树然后处理右子树最后访问当前节点。但Morris遍历的线索机制只能帮助我们回到当前节点无法直接处理“左右都完成”这个条件。一个常用的技巧是把后序遍历转化为“逆序访问右边界”。具体来说对于每个节点当它的左子树处理完后逆序访问从左子节点到当前节点左子树最右节点这条路径上的所有节点。最后再逆序访问从根节点到最右节点这条路径。这个描述听起来很抽象但代码实现有固定的模式。由于Morris后序在实际中用的不多这里不展开完整代码但你需要知道它的存在和基本思路。如果面试中被问到能说出“利用右边界逆序访问”这个核心思想基本就够用了。4.4 Morris遍历的适用场景与局限性Morris遍历最大的优势是空间复杂度O(1)不需要额外的数据结构。这在内存受限的环境中非常有用比如嵌入式系统或者处理超大规模数据时。但Morris遍历也有局限性。首先它会临时修改树的结构虽然最后会恢复但在多线程环境下会有问题。如果多个线程同时遍历同一棵树临时线索会导致数据竞争。其次Morris遍历的代码比递归和栈版本更复杂容易写错调试也更困难。最后Morris遍历的时间常数比递归和栈版本大因为需要频繁地查找前驱节点。虽然时间复杂度都是O(n)但实际运行时间可能更长。我的建议是在大多数业务场景中递归或栈版本足够了。只有在内存非常紧张、或者明确要求O(1)空间复杂度时才考虑Morris遍历。不要为了炫技而使用它。5. 层序遍历队列驱动的按层访问与变体问题5.1 基础层序遍历队列的使用与层分隔技巧层序遍历和前面三种遍历有本质区别前面三种是深度优先层序是广度优先。实现方式也从栈变成了队列。基础层序遍历的代码很简单把根节点入队然后循环出队、访问、把左右子节点入队。但这里有一个关键问题如何区分每一层如果只是简单地把所有节点依次出队得到的是一个扁平的列表无法知道哪些节点属于同一层。解决方法是记录每一层的节点数量。在每一轮循环开始时先获取当前队列的大小这个大小就是当前层的节点数。然后只处理这么多节点处理完后队列中剩下的就是下一层的节点。def level_order(root): if not root: return [] from collections import deque queue deque([root]) result [] while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这个“层分隔”技巧是层序遍历的核心很多变体问题都基于它。比如“二叉树的右视图”只需要在每一层中取最后一个节点“二叉树的层平均值”只需要在每一层中计算平均值“二叉树的最大宽度”需要记录每个节点的位置索引。5.2 层序遍历的变体锯齿形、右视图与最大宽度锯齿形层序遍历要求奇数层从左到右偶数层从右到左。实现方法是在基础层序遍历的基础上根据层数决定是否反转当前层的列表。或者使用双端队列奇数层从尾部添加偶数层从头部添加。右视图要求返回每一层最右边的节点。在层序遍历中每一层的最后一个节点就是右视图的一部分。只需要在每层循环中当处理到最后一个节点时把它的值加入结果。最大宽度要求计算每一层中最左和最右非空节点之间的宽度。这个问题的难点在于空节点的处理。一个常用的技巧是给每个节点编号根节点编号为1左子节点为2i右子节点为2i1。这样每一层的宽度就是最右节点编号减去最左节点编号加1。但这样编号在树很深时会导致数字溢出所以实际实现中通常只记录相对位置。这些变体问题的核心都是层序遍历的框架只是在访问节点时增加了额外的逻辑。掌握了基础框架这些变体都不难。5.3 层序遍历与深度优先遍历的转换关系层序遍历和深度优先遍历看起来是两种完全不同的思路但它们之间是有联系的。层序遍历按层访问深度优先遍历按路径访问。在某些问题中两种思路都可以解决只是效率不同。比如“二叉树的最大深度”深度优先遍历可以用递归轻松解决层序遍历也可以在处理每一层时累加深度。再比如“判断二叉树是否对称”深度优先遍历可以用递归比较左右子树层序遍历也可以逐层比较。选择哪种遍历方式取决于具体问题的特点。如果需要按层处理信息层序遍历更自然如果需要沿着路径处理信息深度优先遍历更合适。在实际面试中面试官有时会要求用两种方式分别实现同一个功能这时候就需要灵活切换思路。6. 实际项目中的遍历选型与性能对比6.1 不同遍历方式的性能对比与选型建议把前面讲的几种遍历方式放在一起对比可以从时间复杂度、空间复杂度、代码复杂度、适用场景几个维度来看。遍历方式时间复杂度空间复杂度代码复杂度适用场景递归O(n)O(h)低树深度可控、可读性优先栈非递归O(n)O(h)中树深度大、需要避免栈溢出MorrisO(n)O(1)高内存受限、明确要求O(1)空间层序O(n)O(w)低按层处理、广度优先问题这里的h是树的高度w是树的最大宽度。对于平衡二叉树h约等于log nw约等于n/2。对于退化二叉树h等于nw等于1。选型建议大多数业务场景用递归就够了代码清晰、维护方便。如果树的深度可能很大或者运行环境栈空间有限用栈非递归。如果内存非常紧张考虑Morris。如果需要按层处理用层序。6.2 遍历在树结构操作中的典型应用遍历不是孤立存在的它是很多树操作的基础。比如树的序列化与反序列化先序遍历可以用于序列化中序遍历可以用于验证二叉搜索树。树的复制先序遍历可以用于复制一棵树先创建根节点再递归复制左右子树。树的镜像后序遍历可以用于交换左右子树因为需要先处理完左右子树再交换。路径求和深度优先遍历可以用于查找从根到叶子的路径和。最近公共祖先后序遍历可以用于查找两个节点的最近公共祖先。这些应用都依赖于遍历框架只是在访问节点时增加了额外的逻辑。理解了遍历的本质这些应用都不难实现。6.3 手写遍历代码的常见错误与调试技巧手写遍历代码时常见的错误包括先序非递归入栈顺序写反中序非递归忘记处理右子树后序非递归判断条件不完整Morris遍历忘记拆除线索层序遍历忘记记录层大小调试技巧先用一棵简单的树比如只有三个节点手动模拟代码执行过程画出栈或队列的变化。如果结果不对逐步检查每个节点的处理顺序。对于Morris遍历可以在建立和拆除线索时打印日志观察树的结构变化。还有一个实用的技巧写一个辅助函数把遍历结果和预期结果对比。预期结果可以通过递归版本生成因为递归版本最容易验证正确性。如果非递归版本的结果和递归版本一致基本可以认为是对的。7. 一些踩过坑之后才明白的经验递归遍历看起来简单但栈溢出是真的会发生的。我在一个项目中处理用户自定义的树结构没有对深度做限制结果遇到极端输入直接崩溃。后来加了深度检查超过阈值就切换到非递归实现。这个教训是永远不要假设输入是友好的。Morris遍历的代码我写过好几次每次都要重新推导一遍。后来我总结了一个口诀“有左找前驱无左直接走前驱右为空建立线索往左走前驱右为当前拆除线索访问往右走。”这个口诀帮我省了很多推导时间。但即便如此我仍然不建议在生产环境中使用Morris除非有明确的O(1)空间需求。代码复杂度和调试成本太高了。层序遍历的层分隔技巧我一开始总是忘记记录层大小导致所有节点混在一起。后来养成了一个习惯只要写层序遍历第一件事就是写level_size len(queue)。这个习惯帮我避免了很多低级错误。最后说一个关于遍历选型的体会不要为了追求“高级”而使用复杂的实现。递归能解决的问题不要用非递归栈能解决的问题不要用Morris。代码是给人看的可读性和可维护性永远比“炫技”重要。当然面试场景除外面试官就是想看你知不知道这些高级方法。
