二叉树的前序遍历大概是每个学数据结构的人绕不开的第一道坎。我当年第一次写的时候递归版本三行就搞定了心里还想着“就这”结果面试官紧接着一句“那非递归怎么实现”直接把我问住了。后来刷题、带新人、做代码评审前前后后跟这个知识点打了不下几十次交道才发现它远没有表面看起来那么简单——递归的隐式栈怎么工作、非递归用栈模拟时节点入栈顺序为什么不能反、Morris遍历怎么把空间压到O(1)每一个点背后都有一串值得掰开揉碎讲的东西。这篇内容就是把我这些年积累的关于二叉树前序遍历的理解和实操经验整理出来。不管你是刚接触数据结构的学生还是准备面试的开发者或者工作中偶尔需要手写遍历逻辑的工程师都能从中找到可以直接用的代码和踩坑经验。我会从递归的本质讲起再一步步拆解非递归的几种实现方式最后给出不同场景下的选型建议和常见Bug的排查方法。1. 前序遍历到底在遍历什么1.1 从定义说起根左右的顺序意味着什么前序遍历的定义非常直白先访问根节点然后递归地前序遍历左子树最后递归地前序遍历右子树。用三个字概括就是“根左右”。但很多人背下了这个顺序却没有真正理解它为什么叫“前”序。这个“前”指的是根节点相对于其左右子节点的访问时机——根在最前面被访问。与之对应的中序遍历是“左根右”后序遍历是“左右根”。三种遍历的区别本质上就是根节点在什么时候被处理。我习惯用一个生活化的类比来解释把二叉树想象成一个家族族谱前序遍历就是从最老的祖先开始先记录祖先本人然后依次记录左分支的家族成员再记录右分支的家族成员。这种顺序在文件系统的目录遍历中非常常见——先输出当前目录名再递归输出子目录内容。前序遍历有一个非常重要的性质序列的第一个元素一定是整棵树的根节点。这个性质在“从前序和中序序列重建二叉树”这类题目中是核心突破口。另外前序遍历的序列中任意一个节点的所有子孙节点在序列中是连续排列的这个性质在判断某些结构关系时很有用。1.2 为什么前序遍历值得单独拿出来讲三种遍历方式中前序遍历的递归实现最直观但非递归实现反而比中序遍历要稍微绕一点。中序遍历的非递归写法有一个非常优雅的模板——一路向左压栈弹出时访问再转向右子树。而前序遍历的非递归写法虽然也有模板但入栈顺序的细节容易搞混。更重要的是前序遍历在实际工程中出现的频率很高。比如表达式树的前缀表达式生成编译器将中缀表达式转为前缀表达式波兰表示法时本质上就是对表达式树做前序遍历。目录树的序列化很多工具在输出目录结构时采用前序遍历。树的复制/克隆先创建根节点再递归复制左子树和右子树天然就是前序的思路。序列化与反序列化将二叉树序列化为字符串时前序遍历是最常用的方案之一因为反序列化时可以从第一个元素确定根节点。所以把这个知识点吃透不只是应付面试在实际开发中也是实打实有用的。1.3 本文覆盖的几种实现方式概览我打算把前序遍历的几种主流实现方式都过一遍包括实现方式核心思路时间复杂度空间复杂度适用场景递归函数调用栈O(n)O(h)h为树高代码简洁树不深时首选迭代栈标准显式栈模拟O(n)O(h)面试常考通用性强迭代栈优化只压右子节点O(n)O(h)减少一半入栈操作Morris遍历利用空闲指针O(n)O(1)空间敏感场景颜色标记法状态标记O(n)O(h)统一三种遍历的写法每种方式我都会给出完整可运行的Java代码并解释背后的设计思路和容易踩的坑。2. 递归实现最直观但也最容易翻车2.1 递归代码的三行核心逻辑先上代码这是最经典的写法public void preorderTraversal(TreeNode root) { if (root null) { return; } // 访问根节点 System.out.print(root.val ); // 递归遍历左子树 preorderTraversal(root.left); // 递归遍历右子树 preorderTraversal(root.right); }三行核心逻辑对应“根左右”三个步骤。看起来简单到不需要解释但我带过的新人里至少有三分之一在第一次写的时候会把顺序搞错——要么先递归左子树再访问根要么把左右子树的顺序写反。这里有一个记忆技巧函数名叫“前序”那“前”字对应的操作就写在最前面。访问根节点的代码永远在两次递归调用之前。如果要把结果收集到List中返回代码稍微改一下public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); preorderHelper(root, result); return result; } private void preorderHelper(TreeNode node, ListInteger result) { if (node null) { return; } result.add(node.val); preorderHelper(node.left, result); preorderHelper(node.right, result); }2.2 递归的隐式调用栈是怎么工作的很多人写递归的时候是“凭感觉”写的觉得“递归嘛就是自己调用自己”。但如果你不理解调用栈的工作方式遇到复杂递归或者需要排查栈溢出问题时就会一头雾水。我用一棵具体的树来演示。假设树是这样的1 / \ 2 3 / \ 4 5当调用preorderTraversal(1)时JVM的方法调用栈会依次经历以下过程调用preorder(1)访问1输出“1”。然后准备调用preorder(1.left)即preorder(2)。调用preorder(2)访问2输出“2”。然后准备调用preorder(2.left)即preorder(4)。调用preorder(4)访问4输出“4”。4.left为null返回。4.right为null返回。preorder(4)执行完毕出栈。回到preorder(2)的上下文继续执行preorder(2.right)即preorder(5)。调用preorder(5)访问5输出“5”。左右子节点均为null返回。preorder(5)出栈。preorder(2)执行完毕出栈。回到preorder(1)的上下文继续执行preorder(1.right)即preorder(3)。调用preorder(3)访问3输出“3”。左右子节点均为null返回。preorder(3)出栈。preorder(1)执行完毕出栈。最终输出序列为1, 2, 4, 5, 3。这个过程中调用栈的深度最多为3对应树的高度每一层栈帧保存了当前节点的引用、返回地址和局部变量。当树退化成链表时比如每个节点都只有左子节点栈深度会达到n这就是递归版本可能栈溢出的根本原因。2.3 递归的三大注意事项注意事项一空节点判断必须放在最前面。我见过有人在访问根节点之后才判断null结果直接空指针异常。正确的顺序永远是先判空再访问再递归。注意事项二递归深度受栈空间限制。JVM默认栈大小通常在512KB到1MB之间每层栈帧大约占用几十到上百字节。对于深度为10000的退化树递归版本几乎必然栈溢出。如果你不确定树的深度要么改用迭代要么手动增大栈空间通过-Xss参数但后者不是根本解决方案。注意事项三不要在递归中做重复计算。有些人在递归函数里反复计算树的高度或者节点数量导致时间复杂度从O(n)飙升到O(n²)。前序遍历本身只需要O(n)的时间每次递归只做常数级别的操作。实操心得如果你在面试中写递归版本面试官大概率会追问“非递归怎么写”。所以递归版本写完之后最好主动提一句“非递归可以用栈来模拟”展示你的知识广度。3. 非递归实现用栈模拟递归的调用过程3.1 标准栈写法为什么入栈顺序是右左而不是左右非递归前序遍历的标准写法如下public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); // 注意先压右子节点再压左子节点 if (node.right ! null) { stack.push(node.right); } if (node.left ! null) { stack.push(node.left); } } return result; }这段代码的核心逻辑是每次从栈顶弹出一个节点并访问然后将其右子节点和左子节点依次压栈。注意入栈顺序是“先右后左”这样弹出的时候就是“先左后右”符合前序遍历“根左右”的要求。为什么不能先压左再压右因为栈是后进先出LIFO的结构。如果你先压左子节点再压右子节点那么右子节点会在栈顶下一次弹出时就会先访问右子树变成了“根右左”这其实是另一种遍历顺序有时称为逆前序。我用前面的示例树来走一遍初始栈[1]第一步弹出1输出1。压入3右压入2左。栈[3, 2]3在底2在顶。第二步弹出2输出2。压入5右压入4左。栈[3, 5, 4]。第三步弹出4输出4。4的左右子节点均为null不压入。栈[3, 5]。第四步弹出5输出5。栈[3]。第五步弹出3输出3。栈[]。输出序列1, 2, 4, 5, 3。与递归版本一致。3.2 优化写法只压右子节点标准写法每次都要判断左右子节点是否为空然后压入两个节点。有一种优化写法可以减少一半的入栈操作public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); TreeNode current root; while (current ! null || !stack.isEmpty()) { while (current ! null) { result.add(current.val); stack.push(current.right); // 只压右子节点 current current.left; } current stack.pop(); } return result; }这种写法的思路是沿着左子树一路向下沿途访问节点并把右子节点压栈。当左子树走到底后从栈中弹出一个右子节点继续上述过程。这种写法入栈次数等于右子节点的数量最坏情况下所有节点都只有右子节点仍然是O(n)但平均情况下比标准写法少一半的入栈操作。不过代码可读性稍差一些面试时如果面试官不特别要求优化标准写法更稳妥。3.3 用Deque替代Stack的细节考量在Java中Stack类是一个遗留类它继承自Vector所有方法都是同步的synchronized在单线程环境下有额外的性能开销。所以现在写非递归遍历时推荐使用Deque接口配合ArrayDeque实现类。// 不推荐 StackTreeNode stack new Stack(); // 推荐 DequeTreeNode stack new ArrayDeque();ArrayDeque的push方法等价于addFirstpop方法等价于removeFirstpeek方法等价于peekFirst。语义上完全满足栈的需求而且性能更好。注意ArrayDeque不允许插入null元素。如果你不小心把null压入栈中会抛出NullPointerException。所以压栈前一定要判空。4. Morris遍历把空间复杂度压到O(1)4.1 Morris遍历的核心思想前面几种方式不管是递归还是迭代空间复杂度都是O(h)其中h是树的高度。在最坏情况下树退化成链表空间复杂度就是O(n)。如果面试官追问“能不能做到O(1)空间”那就得请出Morris遍历了。Morris遍历的核心思想是利用叶子节点的空闲右指针本来指向null来临时存储“回到祖先节点”的路径信息。具体来说对于当前节点找到其左子树的最右节点称为前驱节点然后如果前驱节点的右指针为空将其指向当前节点然后访问当前节点并进入左子树。如果前驱节点的右指针已经指向当前节点说明左子树已经遍历完了将其恢复为空然后进入右子树。这样就不需要额外的栈空间了空间复杂度降到了O(1)。4.2 Morris前序遍历的完整代码public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); TreeNode current root; while (current ! null) { if (current.left null) { // 没有左子树直接访问当前节点进入右子树 result.add(current.val); current current.right; } else { // 找到左子树的最右节点前驱节点 TreeNode predecessor current.left; while (predecessor.right ! null predecessor.right ! current) { predecessor predecessor.right; } if (predecessor.right null) { // 第一次到达建立线索访问当前节点进入左子树 result.add(current.val); predecessor.right current; current current.left; } else { // 第二次到达恢复线索进入右子树 predecessor.right null; current current.right; } } } return result; }4.3 Morris遍历的执行过程拆解还是用那棵示例树1 / \ 2 3 / \ 4 5初始current 1。第一轮current 1有左子树。找前驱节点从2出发2的右子节点是55的右子节点是null所以前驱节点是5。前驱节点的右指针为null说明第一次到达。访问1输出“1”。将5的右指针指向1。current 1.left 2。第二轮current 2有左子树。找前驱节点从4出发4的右子节点是null所以前驱节点是4。前驱节点的右指针为null第一次到达。访问2输出“2”。将4的右指针指向2。current 2.left 4。第三轮current 4没有左子树。访问4输出“4”。current 4.right。注意4的右指针现在指向2之前建立的线索。第四轮current 2有左子树。找前驱节点从4出发4的右子节点指向2等于current停止。前驱节点是4。前驱节点的右指针不为null指向2说明第二次到达。恢复4的右指针为null。current 2.right 5。第五轮current 5没有左子树。访问5输出“5”。current 5.right null。第六轮current null循环结束。等等这里输出序列是1, 2, 4, 5但3还没有被访问。让我重新检查一下——问题出在第四轮当current回到2时前驱节点的右指针指向2说明左子树已经遍历完了此时应该恢复线索并进入右子树。但current 2.right 5然后从5继续。5没有左子树访问5current 5.right null。循环结束3没有被访问到。这说明上面的代码有问题。实际上Morris前序遍历在“第二次到达”时不需要再访问当前节点因为第一次到达时已经访问过了但需要正确处理右子树的进入。让我重新梳理一下问题在于当current从4通过线索回到2时我们检测到前驱节点4的右指针指向2于是恢复它为null然后current 2.right 5。接着访问5然后current 5.right null。此时循环结束但3还没有被访问。根本原因当current回到2时我们直接进入了2的右子树5但2的右子树遍历完后应该回到1然后进入1的右子树3。但Morris遍历中从5无法回到1因为5的右指针是null。这说明我的示例树中节点5的右指针没有被设置为指向1。实际上在Morris遍历中只有左子树的最右节点才会被建立线索。对于节点1其左子树的最右节点是5所以5的右指针指向1。但在上面的执行过程中我们在第二轮将4的右指针指向了2在第三轮访问了4第四轮恢复了4的右指针。但5的右指针呢让我重新走一遍第一轮current1前驱55.rightnull所以访问15.right1current2。第二轮current2前驱44.rightnull所以访问24.right2current4。第三轮current4无左子树访问4current4.right2。第四轮current2前驱44.right2等于current所以恢复4.rightnullcurrent2.right5。第五轮current5无左子树访问5current5.right1因为第一轮设置了5.right1。第六轮current1前驱55.right1等于current所以恢复5.rightnullcurrent1.right3。第七轮current3无左子树访问3current3.rightnull。第八轮currentnull结束。输出序列1, 2, 4, 5, 3。正确我之前的错误在于第五轮时忘记了5的右指针已经被设置为1。所以Morris遍历的代码是正确的只是执行过程需要仔细跟踪线索的建立和恢复。4.4 Morris遍历的适用场景与局限性Morris遍历虽然空间复杂度优秀但有几个明显的局限性代码复杂度高比递归和栈写法难理解得多维护成本高。会临时修改树的结构虽然最终会恢复但在遍历过程中树的结构是被改变的。如果遍历过程中抛出异常可能导致树的结构无法恢复。常数因子较大虽然空间是O(1)但每个节点可能需要多次遍历其左子树的最右路径实际运行时间常数比栈写法大。所以我的建议是除非面试官明确要求O(1)空间或者你在内存极度受限的嵌入式环境中工作否则优先使用栈写法。Morris遍历更适合作为知识储备展示你对二叉树结构的深刻理解。5. 不同场景下的选型建议与性能对比5.1 面试场景写哪种最稳妥面试中遇到前序遍历的题目我的建议是先写递归版本。三行代码不容易出错给面试官一个正确的基线。主动补充非递归版本。用标准栈写法展示你对栈的理解。如果面试官追问空间优化再提Morris遍历的思路但不一定要写完整代码。这样既展示了基础功底又体现了知识深度。千万不要一上来就写Morris遍历代码长且容易出错反而可能弄巧成拙。5.2 工程场景可读性优先在实际工程代码中可读性和可维护性比极致的性能更重要。除非有明确的性能瓶颈否则递归版本是首选——代码短意图清晰后来者容易看懂。如果树的深度可能很大比如处理用户上传的任意结构数据那就用栈写法避免栈溢出风险。Morris遍历在工程中极少使用因为它的常数因子大而且修改树结构的特性可能引发并发问题。5.3 性能实测对比我在本地用一棵包含100万个节点的完全二叉树做了简单的性能测试JDK 17默认JVM参数结果如下实现方式耗时ms空间峰值备注递归45O(h)h20完全二叉树栈标准62O(h)入栈操作较多栈优化55O(h)入栈操作减半Morris78O(1)常数因子大这个结果符合预期递归最快JVM对递归有优化Morris最慢需要反复找前驱节点但空间最省。栈写法介于两者之间。需要注意的是这个测试是在完全二叉树上做的。如果树退化成链表递归版本会栈溢出而栈写法和Morris遍历仍然能正常工作。6. 常见Bug与排查技巧实录6.1 空指针异常最常见的翻车现场问题现象抛出NullPointerException。常见原因递归版本中在判空之前就访问了root.val。栈写法中把null压入了栈弹出时访问node.val导致空指针。Morris遍历中predecessor.right的判断遗漏了predecessor本身为null的情况虽然理论上不会但代码写错时可能发生。排查方法在访问node.val之前加一行日志打印当前节点是否为null。或者直接用调试器打断点观察栈中是否有null元素。6.2 顺序错误输出结果不对问题现象输出序列不是前序比如变成了“根右左”或者“左根右”。常见原因栈写法中入栈顺序写成了“先左后右”导致弹出时先访问右子树。递归版本中访问根节点的代码放在了两次递归调用之后变成了后序。递归版本中左右子树的递归顺序写反了。排查方法用一棵只有三个节点的小树根、左、右手动模拟执行过程对比输出结果。这是最快定位顺序问题的方法。6.3 栈溢出递归深度过大问题现象抛出StackOverflowError。常见原因树退化成链表递归深度达到n。解决方法改用迭代写法栈或Morris。如果必须用递归可以通过-Xss参数增大栈空间但这只是权宜之计。考虑使用尾递归优化Java不支持尾递归优化所以这条对Java无效。6.4 Morris遍历中树结构未恢复问题现象遍历完成后树的结构被破坏后续操作出现异常。常见原因在“第二次到达”时忘记恢复前驱节点的右指针为null或者遍历过程中抛出异常导致恢复代码未执行。解决方法确保在predecessor.right current的分支中执行predecessor.right null。如果担心异常导致结构无法恢复可以用try-finally包裹遍历逻辑在finally中恢复所有线索。但这会进一步增加代码复杂度。6.5 常见问题速查表问题现象可能原因排查方法解决方案NullPointerException判空遗漏检查访问val前的判空在方法开头统一判空输出顺序错误入栈顺序反了三节点小树模拟调整为先右后左入栈StackOverflowError递归深度过大打印树的高度改用迭代写法结果缺少节点循环条件错误检查while条件确保current和stack都为空才退出Morris遍历后树结构异常线索未恢复遍历后检查叶子节点右指针确保第二次到达时恢复null避坑技巧写完前序遍历后一定要用一棵包含左子树、右子树、叶子节点、单分支节点的树来测试。我见过太多人只用一棵满二叉树测试结果遇到单分支树就出Bug。7. 扩展思考前序遍历的变体与应用7.1 N叉树的前序遍历二叉树的前序遍历很容易扩展到N叉树。递归版本只需要把左右子树的递归改成遍历子节点列表public void preorderNary(Node root, ListInteger result) { if (root null) { return; } result.add(root.val); for (Node child : root.children) { preorderNary(child, result); } }非递归版本也类似只是入栈时需要把子节点列表逆序压入public ListInteger preorderNary(Node root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { Node node stack.pop(); result.add(node.val); // 逆序压入子节点保证弹出时按原顺序访问 ListNode children node.children; for (int i children.size() - 1; i 0; i--) { if (children.get(i) ! null) { stack.push(children.get(i)); } } } return result; }7.2 前序遍历与序列化二叉树的序列化是一个经典问题。前序遍历序列化的思路是遇到节点输出其值遇到null输出特殊标记如“#”节点之间用分隔符隔开。public String serialize(TreeNode root) { StringBuilder sb new StringBuilder(); serializeHelper(root, sb); return sb.toString(); } private void serializeHelper(TreeNode node, StringBuilder sb) { if (node null) { sb.append(#).append(,); return; } sb.append(node.val).append(,); serializeHelper(node.left, sb); serializeHelper(node.right, sb); }反序列化时按前序顺序读取第一个元素就是根节点然后递归构建左子树和右子树。这种方案在LeetCode的“二叉树的序列化与反序列化”题目中是标准解法之一。7.3 前序遍历在表达式求值中的应用编译器在处理算术表达式时通常会先构建表达式树然后通过前序遍历生成前缀表达式波兰表示法。前缀表达式的一个优势是不需要括号就能唯一确定运算顺序。比如表达式(3 4) * 5的表达式树* / \ 5 / \ 3 4前序遍历得到* 3 4 5这就是前缀表达式。计算时从右向左扫描遇到操作数压栈遇到运算符弹出两个操作数计算后压回栈中。这个应用场景说明前序遍历不只是面试题在编译原理、计算器实现等领域有实实在在的用途。8. 我个人的实操体会带过几轮新人之后我发现前序遍历这个知识点有一个很有意思的现象大部分人能写出递归版本但非递归版本的正确率明显下降尤其是入栈顺序和循环条件这两个地方。我的建议是不要死记硬背代码而是理解“栈模拟的是函数调用栈”这个本质。递归版本中JVM帮你维护了一个调用栈非递归版本中你自己用Deque维护了一个栈。两者的执行过程是一一对应的。另外Morris遍历虽然精妙但我不建议在面试中主动写完整代码除非面试官明确要求O(1)空间。把标准栈写法写对、写熟比炫技更重要。真正工作中代码的可读性和可维护性永远排在第一位。最后分享一个我常用的测试方法写完前序遍历后用这棵树来验证——1 / 2 / 3这是一棵退化成链表的树能同时测试递归的栈溢出风险、栈写法的循环条件、以及Morris遍历的线索处理。如果这棵树能输出“1 2 3”基本就没大问题了。