分享｜简化实现非递归的二叉树遍历 —— 本来想说最简洁的实现然而程序虽简单但教程写完一看可能也不是特别容易理解

发布时间：2025-11-28 02:18

享受过程，而非结果，简单快乐最实在 #生活乐趣# #日常生活趣事# #简单快乐的生活哲学# #日常生活智慧#

背景

二叉树的遍历是常见且常用的算法。递归版写起来也很简单，无论是哪一种顺序遍历：

def traverse(node): if node is None: return # 该句实现先序遍历 # print(node.val) traverse(node.left) # 该句实现中序遍历 # print(node.val) traverse(node.right) # 该句实现后序遍历 # print(node.val)

但到了非递归版，就完全不是这样了。

首先，网上有很多文章来讲解如何实现非递归版的遍历，这就说明了这个问题并不简单，至少看起来不简单。其次，三种遍历用非递归实现时，做法也截然不同，这让人感觉很迷惑也很恼火。我学了很多次，但都没有彻底学会。

想法

本文是又一个对非递归版实现的尝试，希望能做到比以往的任何版本都简洁。

本为是基于一个简单的观察，递归版的实现简洁，无非就是编译器提供了函数调用栈，支持了递归这一特性。那么，如果我们可以自己模拟递归，是不是也能很简洁很统一地实现二叉树的三种遍历呢？

我们以通常认为非递归版最难实现的后序遍历为例进行分析。

我们再次观察一下递归实现。

在递归函数中，有两次对自身（traverse）的调用。我们可以按照这两次调用将函数体 split 成三部分：当 traverse(node) 被调用时，假如 node 非空，函数会执行到 traverse(node.left) 为止，然后函数调用栈保存当前调用信息，转而执行新的函数调用。当该分支完全结束时，程序又回到了 traverse(node.left) 的下一句 traverse(node.right) 继续执行。类似的事情发生了，该函数执行被打断，直到分支完全结束时才会返回，继续执行下一句 print(node.val)。

也就是说，在递归函数执行过程中，可以分为三个阶段，第一个阶段执行被 traverse(node.left) 打断，第二阶段被 traverse(node.right) 打断，第三阶段执行完剩余语句，函数正常退出。我们只需要记录函数执行了几个阶段，就知道后面再次返回该函数继续执行时应该从哪个语句接着执行下去。

实现

按照这个思路，我们不难写出非递归版的后序遍历了（就是将递归版翻译了一遍）：

def non_recur_traverse(root): stack = [(root, 0)] while stack: node, t = stack.pop() if t == 0: if node is None: continue stack.append((node, t + 1)) stack.append((node.left, 0)) elif t == 1: stack.append((node, t + 1)) stack.append((node.right, 0)) else: print(node.val)

stack 就是我们自己模拟的函数调用栈，(node, t) 表示对 node 的函数调用已经进行了 t 个阶段。

不难发现，只要对上述代码稍作修改，我们也可以实现前序遍历和中序遍历。

另外，其实任何递归函数都可以按这种方式实现，只要记得保存所有函数调用信息即可，毕竟我们自己实现了函数调用栈！

ps:
附上真实代码：