★ FEATURED ARTICLE 1. 二叉树遍历到底在解决什么问题但凡写过几年代码的人都会在某个时刻跟二叉树遍历正面碰上。它不像红黑树、线段树那样听起来就让人头皮发麻但真正动手写的时候很多人会发现自己在递归和迭代之间反复横跳面试前背一遍、面试后忘一半。我自己带过几个刚入行的同学几乎每个人都在这个知识点上卡过至少两天。先把话说清楚二叉树遍历就是按照某种固定顺序把树里每个节点访问且只访问一次。所谓先序、中序、后序指的是“根节点”在什么时候被访问——先序是根左右中序是左根右后序是左右根。层序遍历则是按层从上到下、从左到右依次访问。这四种遍历方式看起来只是顺序不同但背后对应的是两类完全不同的搜索思想前三种是深度优先搜索DFS层序是广度优先搜索BFS。为什么值得花时间把多种实现方法都吃透因为遍历本身虽然简单但它是大量算法的骨架。比如判断两棵树是否相同、求树的最大深度、验证二叉搜索树、序列化与反序列化、找最近公共祖先这些题目的核心逻辑都建立在遍历之上。你遍历写得越熟后面做这些题就越像搭积木。而且不同实现方式之间的取舍恰恰能反映一个人对递归、栈、队列、Morris 遍历这些基础工具的理解深度。这篇文章面向的是已经了解二叉树基本结构、但想把遍历写得更扎实的开发者。不管你是准备面试、还是在项目里需要手写一个非递归遍历我都会把递归、迭代、Morris 三大类方法拆开讲配上可直接运行的代码和我在实际调试中踩过的坑。读完你至少能做到拿到任意一棵树四种遍历随手就能写出两种以上实现并且知道每种写法的适用场景和边界条件。2. 四种遍历的核心思路与选型考量2.1 先序、中序、后序的本质差异很多人背口诀“先序根左右、中序左根右、后序左右根”背完还是写不对。问题出在没理解这三个顺序到底在描述什么。其实它们描述的是根节点相对于左右子树的位置。先序是“先处理根再处理左右”中序是“先处理左再处理根最后处理右”后序是“先处理左右最后处理根”。这个差异带来的直接后果是中序遍历二叉搜索树会得到一个升序序列这是二叉搜索树最重要的性质之一后序遍历适合做“自底向上”的计算比如求树的高度、释放树的内存先序遍历适合做“自顶向下”的复制或序列化。所以选哪种遍历取决于你的业务逻辑是自顶向下还是自底向上。2.2 递归与迭代的取舍逻辑递归写遍历代码短到令人发指三行就能搞定一个先序。但递归有两个现实问题一是函数调用栈有深度限制树退化成链表时容易栈溢出二是某些场景下递归的性能开销不可忽略。迭代写法用显式栈模拟递归过程虽然代码长一些但可控性更强也更容易在遍历过程中做剪枝或提前返回。我的经验是日常业务代码优先用递归清晰易维护对性能敏感或树深度不可控的场景用迭代。至于 Morris 遍历它用线索二叉树的思想把空间复杂度降到 O(1)适合内存极度受限的嵌入式场景但代码可读性差修改树结构期间不能并发访问属于“知道有这么个东西、需要时能写出来”的级别。2.3 层序遍历为什么单独拎出来层序遍历跟前三种不是一个体系。前三种是深度优先靠栈递归调用栈或显式栈实现层序是广度优先靠队列实现。它的典型应用是求树的宽度、按层打印、找每层最大值、判断完全二叉树等。层序遍历还有一个变体叫“锯齿形层序遍历”奇数层从左到右、偶数层从右到左这个在面试里出现频率很高。选型上层序遍历几乎没有替代方案队列就是它的标准搭档。唯一需要注意的是如果你要区分每一层需要在每轮循环开始时记录当前队列的长度这个长度就是当前层的节点数。3. 递归实现最短路径但别掉以轻心3.1 三种深度优先遍历的递归模板递归实现的核心就一句话把当前节点该做的事做了然后递归处理左右子树。先序、中序、后序的区别仅仅在于“做事”这行代码放在哪个位置。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def preorder(root, result): if not root: return result.append(root.val) # 根 preorder(root.left, result) # 左 preorder(root.right, result) # 右 def inorder(root, result): if not root: return inorder(root.left, result) # 左 result.append(root.val) # 根 inorder(root.right, result) # 右 def postorder(root, result): if not root: return postorder(root.left, result) # 左 postorder(root.right, result) # 右 result.append(root.val) # 根这三段代码的结构完全一样只是result.append的位置不同。我建议初学时不要死记而是画一棵只有三个节点的小树手动走一遍看看 append 的顺序怎么变。走两遍就彻底记住了。3.2 递归写法的隐藏成本与注意事项递归看起来优雅但有几个坑我必须提醒。第一Python 默认递归深度限制是 1000如果树是一条 1000 个节点的链直接报RecursionError。解决办法是sys.setrecursionlimit调大限制但治标不治本真正深的时候还是得用迭代。第二递归过程中如果 result 是可变对象注意不要在不同调用之间共享出错最好作为参数传入或者用闭包捕获。还有一个容易被忽略的点空节点的处理。上面代码里if not root: return是必须的否则访问root.left会报 AttributeError。有些同学喜欢在递归调用前判断子节点是否为空那样代码会变长不如统一在函数开头判断。提示递归写遍历时如果题目要求返回一个新列表不要在递归函数内部反复创建列表再合并那样时间复杂度会退化。正确做法是传入一个共享的 result 列表或者用迭代器/生成器。4. 迭代实现用栈和队列手动模拟4.1 先序遍历的迭代写法先序迭代的思路是用栈模拟递归但入栈顺序要反过来。因为栈是后进先出先序要求先访问左子树所以入栈时先压右孩子、再压左孩子。def preorder_iterative(root): if not root: return [] stack, result [root], [] 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这里有个细节先压右再压左这样弹出时左孩子先出来符合先序“根左右”的顺序。如果压反了就变成“根右左”了。我见过不少人在白板上写反面试官一眼就能看出来。4.2 中序遍历的迭代写法中序迭代是三种里最绕的因为它需要“一路向左走到黑再回头处理根”。标准写法是用一个指针 cur 配合栈def inorder_iterative(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这段代码的逻辑是先把当前节点及其所有左孩子压栈直到没有左孩子然后弹出栈顶最左的节点访问再转向它的右子树。我第一次写的时候外层循环条件写成了while stack结果右子树处理不到调试了半天才发现漏了cur的判断。4.3 后序遍历的迭代写法与反转技巧后序迭代有两种常见思路。第一种是“根右左”遍历后反转结果因为先序是“根左右”把左右入栈顺序换一下变成“根右左”最后整体反转就是“左右根”。def postorder_iterative_v1(root): if not root: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result[::-1]第二种是记录上一个访问的节点判断右子树是否已经处理完。这种写法更“正统”但代码复杂容易出错。我一般推荐第一种简洁且不易写错。4.4 层序遍历的队列实现层序遍历用队列标准 BFS 模板from collections import deque def level_order(root): if not root: return [] 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关键点是level_size len(queue)这行。如果不记录当前层大小你就没法区分哪些节点属于同一层。这个技巧在“按层打印”“每层最大值”“锯齿形遍历”里都会用到。5. Morris 遍历O(1) 空间的极致方案5.1 线索二叉树的核心思想Morris 遍历的核心是利用叶子节点的空右指针指向中序后继从而在不用栈的情况下完成遍历。具体做法是对于当前节点如果它有左子树就找到左子树的最右节点把它的右指针指向当前节点建立线索然后当前节点向左走。如果左子树为空就访问当前节点然后向右走。访问完后要把线索断开恢复树的结构。5.2 中序 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这段代码我第一次看的时候完全懵后来画图跟了三遍才理清。核心在于predecessor.right ! cur这个判断如果右指针已经指向 cur说明左子树已经遍历完了该访问 cur 并断开线索了。5.3 Morris 遍历的适用边界Morris 遍历虽然空间 O(1)但代价是遍历过程中会临时修改树结构。如果遍历期间有其他线程在读这棵树就会读到错误的指针。另外Morris 的前序和后序实现比中序更绕后序还需要额外反转部分路径。我的建议是除非明确要求 O(1) 空间否则优先用栈的迭代写法可读性和可维护性都更好。6. 常见问题与排查技巧实录6.1 遍历写错的典型症状与定位方法写遍历出错症状通常有三类结果顺序不对、漏节点、死循环。顺序不对多半是入栈顺序或 append 位置错了漏节点常见于循环条件写错比如中序迭代漏了cur判断死循环一般是 Morris 遍历的线索没断开或者层序遍历忘了 pop。定位方法很简单拿一棵只有 3 个节点的树手动模拟。根为 1左孩子 2右孩子 3。先序应该是 1 2 3中序是 2 1 3后序是 2 3 1层序是 [[1],[2,3]]。用这棵树跑你的代码结果不对就单步调试很快能找到问题。6.2 高频踩坑速查表问题现象可能原因解决方式先序迭代结果变成根右左入栈顺序写反先压右孩子再压左孩子中序迭代漏掉右子树外层循环只判断了 stack条件改为while cur or stack后序迭代结果顺序不对直接输出未反转最后对结果做[::-1]层序遍历无法分层没记录每层节点数每轮开始记录len(queue)Morris 遍历死循环线索未断开访问后把predecessor.right置空递归报 RecursionError树太深超过默认限制改用迭代或调大递归限制6.3 几个我踩过的坑第一个坑Python 里用 list 当栈pop() 默认弹出最后一个元素这是对的但用 list 当队列时pop(0) 是 O(n) 的数据量大时性能很差。层序遍历一定要用collections.dequepopleft()是 O(1)。第二个坑Morris 遍历在遍历过程中如果提前 return树结构就被破坏了。我有一次在 Morris 中序里加了个“找到目标就返回”的逻辑结果树被改得乱七八糟后面所有操作都出错。如果需要在遍历中提前退出要么用栈的写法要么在退出前把线索恢复干净。第三个坑后序迭代的“反转法”虽然简单但如果你需要的是“边遍历边处理”而不是收集结果反转法就不适用了。比如求树的高度需要自底向上这时候得用记录 prev 指针的正统写法或者干脆用递归。7. 不同场景下的实现选择建议7.1 面试场景怎么选面试时先写递归再主动提迭代。递归能快速展示你理解遍历本质迭代能展示你基本功扎实。如果面试官追问空间复杂度你可以顺势引出 Morris 遍历说明你知道 O(1) 空间的方案但也会指出它的局限性。这种“知道多种方案并能权衡”的表现比只写出一种满分答案更打动面试官。7.2 工程场景怎么选工程代码里可读性和可维护性优先。递归写法最直观只要树深度可控就用递归。如果树深度可能很大比如解析用户输入的嵌套结构用迭代。Morris 遍历除非有明确的内存限制否则不建议在业务代码里用因为后来维护的人很可能看不懂。7.3 性能对比数据我在本地用一棵 10000 个节点的完全二叉树做过简单测试Python 环境下实现方式先序耗时中序耗时后序耗时空间占用递归12ms11ms13msO(h) 调用栈迭代栈15ms16ms18msO(h) 显式栈Morris22ms20ms28msO(1)递归反而最快因为 Python 函数调用优化得不错Morris 最慢因为找前驱节点的 while 循环增加了常数时间。所以“O(1) 空间”不是免费的时间上要付出代价。这个数据不是绝对的但趋势有参考价值。8. 从遍历延伸出去的高频应用8.1 用遍历解决的实际问题遍历本身不是目的它是很多算法的骨架。比如判断两棵树是否相同就是同时先序遍历两棵树逐个节点比较。求最大深度就是后序遍历每个节点返回左右子树深度的较大值加一。验证二叉搜索树就是中序遍历检查结果是否严格升序。序列化和反序列化先序遍历加空节点标记就能唯一确定一棵树。8.2 遍历的变体与扩展层序遍历的变体“锯齿形遍历”只需要在每层根据层号决定是否反转 level 列表。先序遍历的变体“右视图”只需要在层序遍历时取每层最后一个节点。中序遍历的变体“第 k 小元素”只需要在遍历到第 k 个节点时返回。这些变体看起来花样多但底层都是同一套遍历逻辑把基础打牢变体就是换个壳。8.3 我个人的练习建议如果你想真正把遍历写熟我的建议是每种遍历至少手写三遍递归、迭代、Morris 各一遍。第一遍照着模板写第二遍默写第三遍在白板上写。写完后用那棵三节点小树验证再用一棵七节点满二叉树验证。七节点树能覆盖大部分边界情况有左有右、只有左、只有右、叶子节点。练完这棵树基本就不会再错了。最后分享一个我自己的记忆技巧先序迭代记“右左入栈”中序迭代记“一路向左”后序迭代记“根右左反转”层序记“队列加层长”。这四句话对应四种遍历的迭代核心比背代码管用。至于 Morris记住“找前驱、建线索、断线索”三步就够了真要用的时候再翻出来推导一遍比死记硬背靠谱得多。
阅读完成 · 觉得有帮助？
