我最早学二叉树递归遍历的时候心里一直有个疙瘩前序、中序、后序三种写法代码长得几乎一模一样不就是把print挪个位置嘛可一旦自己动手画递归过程脑子就乱成一锅粥。后来带过几届学弟学妹发现这个困惑几乎是所有人共同的坎。这篇就把“递归初相见”时最该搞明白的东西一次说透包括三种遍历姿势的代码、递归调用栈到底是怎样进出的、为什么写二叉树程序总是报运行时错误以及从递归到非递归的进阶思路。适合正在学数据结构、刚被递归折磨过的同学也适合准备面试需要把底層逻辑讲清楚的人。1. 遍历二叉树之前先搞清楚递归的三种底气递归看起来玄乎其实背后的思维方式非常简单把一个大问题拆成若干个和自己同构的小问题小到不能再拆的时候直接给出答案。二叉树遍历就是最典型的例子。但在能写出三种遍历之前得先想明白三件事否则代码就是抄一遍忘一遍。1.1 递归不是玄学函数为什么敢调用自己很多初学者第一次看到函数调用自身脑子里冒出来的问题是它不会死循环吗它不会把自己调爆吗先说结论只要满足两个条件函数调用自己就是完全安全的。第一问题规模在每次调用后都严格变小第二存在一个不能继续拆分的“最小问题”碰到它就直接返回不再调用自己。这两个条件翻译成代码就是递归函数里必须有的两部分终止条件base case直接返回不再递归。递归调用recursive case把问题缩小后继续调用自己。拿“数一个文件夹里有多少个文件”来类比。你打开一个文件夹遇到子文件夹就进去数遇到文件就记一个数。子文件夹里还可能套着子文件夹但总归有个尽头——文件夹不可能无限嵌套。这个“尽头”就是终止条件。二叉树也一样一个节点下面可能挂着左子树和右子树但总归会走到没有孩子的节点再往下走就是空None空就是尽头。1.2 树本身就是递归定义出来的结构为什么二叉树遍历用递归这么顺手因为树的定义本身就是递归的。一段最经典的描述二叉树要么是空树要么由一个根节点加上左右两棵互不相交的二叉树组成。注意这里说的是“两棵二叉树”也就是说每个节点的左孩子和右孩子各自又都是一棵二叉树的根。这就是递归的天然土壤。遍历一棵树 处理根节点 遍历它的左子树 遍历它的右子树。而遍历左子树又等于处理左子树的根 遍历左子树的左子树 遍历左子树的右子树……这样一层层套下去直到遇到空节点。所以不需要把“遍历一颗完整的树”当成一个庞大任务。只需要定义好“怎么处理一个节点以及它的左右孩子”递归会替你把整棵树跑完。同一个逻辑放到代码里就是这样的骨架def traverse(node): if node is None: return # 处理当前节点 traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树这一段骨架看着简单但它是后面所有遍历代码的底座。前序、中序、后序区别只在于“处理当前节点”这句话放在哪个位置。1.3 递归三要素终止条件、递归调用、状态回归除了终止条件和递归调用还有一个容易被忽略的东西状态回归。这个概念在初学阶段尤其重要。递归调用发生时系统会把当前函数的所有局部变量、参数、以及“执行到哪一行”的信息压入调用栈然后才开始执行新一层的函数。当新一层函数返回之后系统会从栈顶恢复之前保存的信息继续往下执行。这个“恢复现场”的过程就是状态回归。生活化的例子是你在读一本套娃结构的书。你翻到第10页里面提到要看附录A于是你夹好书签去看附录A附录A里又提到要看附录B你又夹一个书签去看附录B等附录B看完你拿起上一个书签回到附录A继续读附录A读完再拿起最开始的第10页书签接着往下读。每个“书签”就是一次状态回归的标记。理解了这三件事再去看三种遍历就只剩下“打印语句放哪”这一个问题了。2. 三种遍历姿势的代码对照前序、中序和后序到底差在哪前序、中序、后序这三种叫法指的是“根节点”在整棵树的访问顺序里出现的位置。前序是根最先根-左-右中序是根在中间左-根-右后序是根最后左-右-根。记住这个代码就成功了一半。下面用一棵具体的树来演示。假设二叉树长这样1 / \ 2 5 / \ \ 3 4 6节点值不重要重要的是结构根是1左孩子是2右孩子是52的左孩子是3右孩子是45的右孩子是6。2.1 前序遍历先处理根再深入子树前序遍历的顺序是根节点 → 左子树 → 右子树。代码非常短def preorder(node): if node is None: return print(node.val) # 先处理根 preorder(node.left) # 再遍历左子树 preorder(node.right) # 最后遍历右子树打印结果是1 2 3 4 5 6。前序遍历特别适合用来序列化一棵树或者做目录展示。因为它总是先看到父节点再看到子节点父子的先后关系非常清晰。如果你要把一棵树打印成带缩进的树形结构前序就是最自然的顺序。很多人在实际项目里用前序生成 JSON 结构里的层级信息就是这个道理。2.2 中序遍历左、根、右有序输出的秘密中序遍历的顺序是左子树 → 根节点 → 右子树。代码只需要把打印挪到两行递归之间def inorder(node): if node is None: return inorder(node.left) # 先遍历左子树 print(node.val) # 再处理根 inorder(node.right) # 最后遍历右子树在上面的示例树上打印结果是3 2 4 1 5 6。中序遍历在二叉搜索树BST上的价值是独一无二的对一棵二叉搜索树做中序遍历得到的结果是一个升序序列。这个性质在搜索二叉树相关的题目里几乎必考。比如你写一个“判断一棵树是不是二叉搜索树”的算法最笨但最可靠的办法就是中序遍历看结果是不是严格递增的。如果你学线索二叉树会发现线索化也依赖中序遍历的顺序。因为线索二叉树的本质就是利用中序遍历时节点之间的前驱和后继关系来优化遍历没有中序的序列概念线索化根本无从谈起。2.3 后序遍历先解决孩子再回头处理自己后序遍历的顺序是左子树 → 右子树 → 根节点。代码看着还是那三行只是打印到了最后def postorder(node): if node is None: return postorder(node.left) # 先遍历左子树 postorder(node.right) # 再遍历右子树 print(node.val) # 最后处理根打印结果是3 4 2 6 5 1。后序遍历最典型的应用场景有两个。第一个是删除整棵树你必须先把左右子树删干净才能删当前节点否则会留下悬空的子节点。第二个是自底向上的统计比如计算一棵树的高度depth或者统计每个节点有多少个后代节点都得先拿到子树的结果再汇总到当前节点。这里顺带提一个初学者容易踩的误区有人觉得“后序不就是把前序的 print 挪到最后嘛区别不大”。不是区别不大的问题是访问顺序完全变了。前序先看到的永远是根后序先看到的是最底层的左叶子节点处理逻辑的先后顺序是完全相反的。2.4 三个版本放一起对比把三个函数并排摆着看整体结构几乎一模一样唯一的区别就是打印语句的位置遍历方式访问顺序打印位置典型场景前序根 → 左 → 右递归调用之前序列化、目录展示中序左 → 根 → 右两次递归调用之间二叉搜索树排序输出后序左 → 右 → 根递归调用之后删除树、自底向上统计这段代码的“稳定性”是递归最大的优点想从一种遍历改成另一种只需要移动一行。缺点呢如果你不理解递归过程移动之后只能靠背没法解释为什么是这个结果。所以接下来用最笨但最有效的方法——手画调用栈把三种遍历里到底发生了什么看清楚。3. 用手画一遍递归调用栈打印语句的位置决定一切很多人代码写对了但内心其实并不踏实总觉得递归是个“黑盒”。这里分享一个我现在还在用的笨办法拿一棵很小的树把每一次函数调用展开亲眼看看栈帧是怎么进怎么出的。只要认真画一遍递归就不再是黑盒了。3.1 一棵三层小树的中序追踪为了简化演示用一棵更小的树1 / \ 2 3对根节点 1 调用inorder(1)完整过程如下inorder(1)进入1 不为空于是调用inorder(1.left)也就是inorder(2)。此时inorder(1)的栈帧被压入栈底暂停在“调用左子树”那一行。inorder(2)进入2 不为空调用inorder(2.left)也就是inorder(None)。inorder(2)的栈帧压在上面。inorder(None)进入发现节点为空直接 return。栈顶弹出inorder(None)。回到inorder(2)继续执行“调用左子树”之后的下一行也就是print(2)输出 2。然后inorder(2)调用inorder(2.right)同样为空直接 return。inorder(2)全部执行完毕return。它的栈帧弹出回到inorder(1)。inorder(1)继续执行“调用左子树”之后的下一行也就是print(1)输出 1。然后调用inorder(1.right)也就是inorder(3)同样的流程输出 3。inorder(3)返回后inorder(1)执行完毕整个函数结束。最终输出2 1 3和代码预期完全一致。3.2 调用栈如何记住“回来的路”上面这段过程里最关键的一步是步骤 4 和步骤 7。当inorder(2)返回后系统为什么能知道接下来要执行print(1)答案是调用栈。inorder(1)的栈帧里保存了它自己的局部变量和返回地址。所谓“返回地址”就是当初它调用inorder(2)之后下一行该执行哪条指令的地址。这个机制不需要你手动维护编程语言帮你全做了。但理解它对排查问题非常重要。比如递归层数特别深时系统抛出的错误叫RecursionError: maximum recursion depth exceededPython 里递归深度默认限制约 1000 层本质就是调用栈被填满了。你之前觉得“递归就是云里雾里看不见摸不着”现在可以精确地说递归是层层压栈、弹栈的过程不是玄学。一个很有用的调试技巧是在递归函数里加两行日志观察进出的时机def inorder(node, depth0): if node is None: return print(enter, node.val, at depth, depth) inorder(node.left, depth 1) print(visit, node.val, at depth, depth) inorder(node.right, depth 1) print(exit, node.val, at depth, depth)跑一下这棵树输出会清晰展示每个节点的 enter/visit/exit 顺序。你把这段日志跑熟之后再回头看前序遍历print放在递归调用前面意味着每个节点都在“进入”时被访问后序遍历的print放在末尾意味着每个节点都在“离开”时被访问。打印语句的位置本质上就是“访问根”这个动作在栈帧生命周期里的位置。3.3 用一张表理解三种遍历的进出时机节点状态前序访问时机中序访问时机后序访问时机刚进入函数、还未遍历子树访问根节点不访问不访问左子树遍历完毕、回到当前节点不访问已访问过访问根节点不访问右子树遍历完毕、准备返回不访问已访问过不访问已访问过访问根节点这张表基本就是三种遍历的完整攻略。我的经验是理解“访问根”发生在栈帧从进入到弹出的哪个阶段比背“根左右、左根右、左右根”靠谱得多。前者遇到变体能自己推后者一换场景就傻眼。4. “运行时错误”背后的三个经典坑和一套自查流程搜索热词里有一条叫“写二叉树程序时为什么总是报运行时错误”这句话我太有共鸣了。二叉树题目的逻辑本身通常不难难的往往是那些莫名其妙让你Segmentation fault、RecursionError、AttributeError: NoneType object has no attribute left的瞬间。下面这三个坑是我见过的所有初学二叉树的人几乎都踩过的。4.1 坑一空指针的偷袭最常见的报错场景对一个空节点直接访问属性。if node.left is not None: ...这句代码本身没错但如果你忘了在最前面判断node is None一旦递归到某个没有左孩子的节点node.left就会直接访问空对象程序立刻崩掉。我见过最离谱的版本是一个同学写的遍历函数只判断了node.right结果遇到只有左子树的节点时左边递归进去直接空指针。正确的做法是递归函数一进来就判空def traverse(node): if node is None: return # 到这里 node 一定不为空 traverse(node.left) traverse(node.right)这个习惯一定要养成。不要觉得判空多余它是递归遍历的“安全带”没有它前面所有逻辑都白搭。4.2 坑二终止条件缺失导致的无限递归另一种经典的运行时错误是递归没有终止条件或者终止条件永远到达不了。比如def bad_traverse(node): # 忘记写 if node is None: return print(node.val) bad_traverse(node.left) bad_traverse(node.right)这段代码最终会在某个叶节点处一直递归到空节点然后空节点又继续访问.left/.right栈越压越深直到内存耗尽或者递归深度撞上上限。在 Python 里这个错误的表现通常是RecursionError: maximum recursion depth exceeded在 C 里则可能是栈溢出Stack Overflow表现出来就是进程直接被系统杀掉。排查思路也很简单看错误信息里崩溃的栈顶是不是同一个函数重复出现。如果是十有八九是终止条件的问题。把“进入递归函数第一行判空”这个习惯补齐这个坑基本就填上了。4.3 坑三测试树本身就建错了还有一种特别隐蔽的场景代码看起来全对但报错位置在遍历函数之外。比如你在main里手写建一棵树时把左右孩子接反了或者建树建到一半就跑遍历函数导致传入了一个残缺的结构。我建议所有初学者都写一个简单可靠的建树工具函数把精力留给遍历本身。比如用列表建树None表示空节点class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def build_tree_from_level_order(values): if not values: return None root TreeNode(values[0]) queue [root] idx 1 while idx len(values): current queue.pop(0) if values[idx] is not None: current.left TreeNode(values[idx]) queue.append(current.left) idx 1 if idx len(values) and values[idx] is not None: current.right TreeNode(values[idx]) queue.append(current.right) idx 1 return root这个函数把列表转换成层序对应的二叉树结构None就表示某个位置没有节点。用它建树可以省掉大量手工TreeNode(1)、node1.left node2的重复代码也不容易出现左右接反的低级错误。4.4 完整排查链路与可直接抄的模板如果你现在写二叉树递归遍历一直报错按下面这个顺序查基本能覆盖 90% 的问题看报错类型RecursionError/stack overflow→ 多半是终止条件缺失。AttributeError/Segmentation fault→ 多半是访问了空节点的属性。报错发生在main里而不是遍历函数里 → 多半是建树/传参的问题。在递归函数最开头加打印打印当前节点的值或深度。如果打印的值开始反复出现说明可能出现了循环引用或者终止条件失效。单独打印树的完整结构确认树确实建对了。比如用前序遍历输出一遍看结果是否符合你的预期。不要用全局变量临时补救。先停下代码回到“第一行判空、有终止条件、传参正确”这三个基本点上重新检查。下面是完整的通用模板可以直接抄def preorder(node, resultNone): if result is None: result [] if node is None: return result result.append(node.val) preorder(node.left, result) preorder(node.right, result) return result用这个模板返回值可以直接拿来做断言测试方便验证输出是否符合预期.5. 从递归墙内到墙外非递归遍历与快速排序的同源逻辑学会了递归遍历下一步通常会遇到两个方向一是把递归改成非递归二是拿递归去写其他分治算法比如快速排序。这两件事其实是一件事因为非递归遍历和快速排序非递归背后共用同一套“显式模拟调用栈”的思路。5.1 为什么要跳出递归递归代码短、可读性强但有两个现实问题递归深度受限。当树退化成一条链比如每个节点都只有右孩子时递归深度等于节点数量。几千层可能没事几万层就可能爆栈。性能开销相对高。每次函数调用都要压栈、弹栈维护栈帧。虽然现代编译器对尾递归有优化但二叉树遍历这种非尾递归场景开销是实打实的。所以面试题里经常让你手写非递归遍历考的不是“会不会递归”而是“懂不懂用栈去模拟递归过程”。5.2 前中后序的非递归写法前序遍历的非递归写法最简单因为你只需要保证“先根后左右”的出栈顺序。用一个栈根节点先入栈然后出栈访问再把右孩子入栈、左孩子入栈。因为栈是后进先出先压右再压左左孩子就会先弹出def preorder_iterative(root): if root is None: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) if node.right is not None: stack.append(node.right) if node.left is not None: stack.append(node.left) return result中序遍历的非递归就麻烦一点。递归版本里你要先把左子树全部走到底再访问当前节点然后处理右子树。翻译成显式栈就是一直往左压栈压到空为止然后弹出一个访问再把指针移到它的右孩子继续重复“一直往左压”的过程def inorder_iterative(root): result [] stack [] current root while stack or current is not None: while current is not None: stack.append(current) current current.left current stack.pop() result.append(current.val) current current.right return result这段代码其实就是递归中序遍历的“栈版本”。如果看懂了前面调用栈的进出过程你会发现这个循环的结构和递归版几乎一一对应。后序的非递归版本最绕常见的技巧是用两个栈或者用“前序的镜像”做逆序输出。这里给一个我常用的两栈版本def postorder_iterative(root): if root is None: return [] stack1 [root] stack2 [] while stack1: node stack1.pop() stack2.append(node.val) if node.left is not None: stack1.append(node.left) if node.right is not None: stack1.append(node.right) return stack2[::-1]原理是前序是“根-左-右”如果我们换成“根-右-左”的顺序入栈最后反转一次就得到了“左-右-根”的后序。这段代码理解的关键仍然是明白“栈的进出顺序决定了访问顺序”。5.3 快速排序非递归同一套分治思想的另一种表演很多人背过快排的递归写法却从来没想过它和二叉树前序遍历之间的关系。其实快速排序的分区过程就相当于处理一个节点左右子区间就相当于左右子树。递归版快排长这样def quicksort(nums, left, right): if left right: return pivot partition(nums, left, right) # 处理“根” quicksort(nums, left, pivot - 1) # 处理“左子树” quicksort(nums, pivot 1, right) # 处理“右子树”这和二叉树前序递归遍历的骨架完全同构。你甚至可以把每次分区得到的左右区间看作一棵递归树的两个分支。非递归版快排自然就是用显式栈来模拟这些“待排序区间”def quicksort_iterative(nums): stack [(0, len(nums) - 1)] while stack: left, right stack.pop() if left right: continue pivot partition(nums, left, right) stack.append((left, pivot - 1)) stack.append((pivot 1, right)) return nums有没有发现这个写法和非递归前序遍历几乎一个套路把“处理完当前节点后要处理的子任务”压入栈中然后循环弹出处理。所以学到这里可以总结出一个很通用的思维方式所有递归分治算法都可以拆成“当前节点的处理”和“子问题的压栈”两步。你学会的二叉树递归遍历其实是在给所有分治算法铺路。想通了这一层“递归”这个概念才算真正长到自己身上了。我个人在实际操作中的体会是递归遍历不是靠背模板学会的靠的是亲手把一次递归调用完整展开一遍。展开一次之后前中后序的区别、调用栈的进出时机、非递归为什么要用栈全部会连成一条线。以后再遇到“写二叉树总是报错”的问题你也不会再盯着屏幕发呆而是会像排查任何程序问题一样从错误类型、终止条件、测试数据三个方向快速锁定原因。递归这条路走到这里才算真正“初相见”。