leetcode 二叉树遍历全解:DFS、BFS、双色标记与 Morris 遍历的完整实现
leetcode 二叉树遍历全解:DFS、BFS、双色标记与 Morris 遍历的完整实现
本文基于 leetcode 题解仓库的专题笔记 二叉树的遍历(中文版见 thinkings/binary-tree-traversal.md),系统讲解二叉树的五种遍历实现方式:前序、中序、后序、层序,以及能够统一三种深度优先遍历的双色标记法和 O(1) 空间的 Morris 遍历。读完之后,你将能够针对任意二叉树题目快速选择递归或迭代方案,理解栈与递归的对应关系,并掌握按层输出的标记位技巧。
一、总览:遍历是树题目的底层能力
二叉树作为基础数据结构,遍历作为基础算法,两者的结合产生了大量经典问题。很多题目中都有树遍历的身影——有的是直接考察遍历本身,有的是间接考察:例如要求“找到树中满足条件的节点”时,本质上就要求你先完成一次遍历。
如果掌握了二叉树的遍历,那么其他更复杂的树(多叉树、森林等)对你来说也大概率不再困难。
仓库将二叉树遍历划分为两大类:
- 深度优先遍历(DFS):前序(Preorder)、中序(Inorder)、后序(Postorder),三者的差别仅在于根节点被访问的相对位置,左右子树的相对顺序永远是“先左后右”;
- 广度优先 / 层次遍历(BFS):逐层、从左到右访问节点。中文版笔记补充了一个值得记住的观点:层次遍历其实可以看成“没有提前终止的 BFS”,因此它既可以用 BFS 实现,也可以用 DFS 实现,只是 BFS 更容易写。
DFS 与 BFS 都各有典型应用。仓库中可参考的两个例子是 301. 删除无效的括号(用 BFS 按删除次数分层搜索,保证找到删除数量最少的解)和 609. 在系统中查找重复的文件(用 DFS 递归目录结构)。
对于 DFS,有两个关键点:
- 栈:迭代实现 DFS 时,栈用于保存“待访问但暂不能输出”的节点;
- 递归:树本身就是递归定义的数据结构(树 = 根 + 左子树 + 右子树),递归是 DFS 最自然的表达方式。
对于 BFS,关键点是如何判断每一层的遍历已经完成。答案是引入一个特殊标记(仓库题解中使用 null)作为当前层结束的标识。
DFS 遍历过程图解(来自 DFS 动画):
二、前序遍历(Preorder):根 - 左 - 右
前序遍历的顺序是 根 - 左 - 右,对应题目 144. 二叉树的前序遍历。
2.1 栈迭代算法
由于是“根”先访问,前序迭代实现是所有 DFS 遍历中最直观的:
- 访问根节点,将其压入栈;
- 弹出一个节点,将其右子节点、左子节点依次压入栈(注意入栈顺序:右先左后,这样左子节点会先被弹出);
- 重复步骤 2,直到栈为空。
仓库中 144 号题解 给出的 JavaScript 迭代实现完整体现了这一算法:
// 迭代方案:先根、再左、最后右
if (!root) return [];
const ret = [];
const stack = [root]; // 1. 根节点入栈
let t = stack.pop();
while (t) {
if (t.right) {
stack.push(t.right); // 2. 右子先入栈(后出)
}
if (t.left) {
stack.push(t.left); // 左子后入栈(先出)
}
ret.push(t.val); // 访问当前节点
t = stack.pop();
}
return ret;
同文件还提供了另一种风格的 C++ 实现(problems/144.binary-tree-preorder-traversal.md#L119-L133):沿左链一路压栈并输出,遇到空指针时回退到栈顶的右子树——这种写法与中序遍历的结构非常接近,是理解“迭代与递归互转”的好素材。
2.2 宏观视角:自上而下递归 + 自底向上用栈
如果把前序遍历放到更大的尺度上看,它的过程可以描述为:自顶向下依次访问左侧链,然后自底向上依次访问右侧链。
- “自上而下”的部分可以直接用递归完成;
- “自底向上”的部分则交给栈。
从源码结构看,这种思路与回溯法(backtrack)的处理方式非常相似:递归负责进入子问题,栈负责在返回时重建现场。仓库中专门有一篇 回溯法笔记 展开讨论,而更重要的是:“自上而下 + 自底向上”的视角可以统一前、中、后三种 DFS 遍历,这是本专题最值得记住的一个结论。
三、中序遍历(Inorder):左 - 根 - 右
中序遍历的顺序是 左 - 根 - 右,对应题目 94. 二叉树的中序遍历。
与前序不同,根节点不是第一个输出的,因此不能简单地“弹栈即输出”。栈迭代算法如下:
- 访问根节点,将其压栈;
- 如果存在左子节点,将其压栈,重复此过程直到到达叶子节点——此时栈中保存的是从根到最左叶子的一整条左链(即“根节点和所有左节点都在栈中”);
- 开始弹出栈顶节点;若该节点有右子节点,则右子节点入栈,回到步骤 2 继续。
94 号题解 的 Python 迭代实现是该算法的忠实翻译:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
stack = []
ans = []
cur = root
while cur or stack:
# 步骤 2:沿左链压栈,直到 cur 为空
while cur:
stack.append(cur)
cur = cur.left
# 步骤 3:弹出并访问,转向右子树
cur = stack.pop()
ans.append(cur.val)
cur = cur.right
return ans
同文件还给出了等价的 JavaScript 与 Java 版本(94 号题解),三者的骨架完全一致:while cur or stack → 压左链 → 弹出访问 → 转右子树。
3.1 BST 的重要性质
值得特别指出的是:二叉搜索树(BST)的中序遍历结果是一个有序数组。这一性质可以让不少 BST 相关题目得到简化,例如:
- 230. 二叉搜索树中第K小的元素:中序遍历到第 k 个即停;
- 98. 验证二叉搜索树:中序遍历的结果必须严格递增。
四、后序遍历(Postorder):左 - 右 - 根
后序遍历的顺序是 左 - 右 - 根,对应题目 145. 二叉树的后序遍历。
这一题在 LeetCode 上带 Hard 标签,难度在于根节点最后输出:一个节点只有在两种情况下才能出栈输出——
- 它是叶子节点(
left与right同时为null,判断很直接); - 它的左、右子树都已经遍历过了。
对于条件 2,最朴素的做法是为每个节点都记录一个访问状态,空间复杂度 O(n)。但仓库笔记指出一个更聪明的观察:我们使用的是栈、且输出从叶子开始,因此只需要记录“上一个出栈输出的节点”这一个变量即可判断栈顶的子树是否已完成遍历,空间复杂度降为 O(1)(不计算输出数组与递归/栈本身)。
145 号题解 的 JavaScript 实现中,变量 p 就是这一技巧的落地:
if (!root) return [];
const ret = [];
const stack = [root];
let p = root; // 标识元素,用来判断节点是否应该出栈
while (stack.length > 0) {
const top = stack[stack.length - 1];
if (
top.left === p ||
top.right === p || // 子节点已经遍历过了
(top.left === null && top.right === null) // 叶子元素
) {
p = stack.pop();
ret.push(p.val); // 满足输出条件,出栈并记录
} else {
if (top.right) stack.push(top.right);
if (top.left) stack.push(top.left);
}
}
return ret;
注意循环里并没有每次无条件弹栈:当栈顶节点不满足输出条件时,只压入它的左右子节点并继续观察——这正是“记录当前节点是否已访问”思想的体现。同文件的 C++ 版本用 prev 指针完成了同样的逻辑(145 号题解)。
五、层次遍历(Level Order / BFS)
层次遍历的关键点与总览部分提到的完全一致:如何判断每一层的遍历已经完成。仓库的做法是往队列中放入一个特殊标记 null 来表示当前层的结束。
BFS 遍历过程图解(来自 BFS 动画):
算法步骤(对应题目 102. 二叉树的层序遍历):
- 访问根节点,将其放入 FIFO 队列,同时向队列放入一个特殊标记(此处使用
null); - 出队一个节点;
- 若该节点等于
null,说明当前层所有节点已访问完。再判断队列:若队列已空则什么都不做(遍历结束);否则再放入一个null,为下一层准备结束标记; - 若该节点不是
null,说明当前层还没遍历完,将它的左、右子节点依次入队。
102 号题解 的 JavaScript 实现:
var levelOrder = function (root) {
if (!root) return [];
const items = []; // 存放所有层的结果
const queue = [root, null]; // null 作为每层的结束标记
let levelNodes = []; // 存放当前层的节点值
while (queue.length > 0) {
const t = queue.shift();
if (t) {
levelNodes.push(t.val);
if (t.left) queue.push(t.left);
if (t.right) queue.push(t.right);
} else {
// 一层遍历完了:结算当前层,为下一层准备标记
items.push(levelNodes);
levelNodes = [];
if (queue.length > 0) {
queue.push(null); // 注意:必须先判断队列非空,否则会无限循环
}
}
}
return items;
};
题解中还给出了一个等价的替代方案(C++ 迭代版):不在队列中放入 null,而是在每轮 while 循环开始时先记录当前队列长度 sz,然后只处理 sz 个节点,从而天然地按层切分结果。两种方案时间复杂度都是 ,空间复杂度 (N 为节点总数)。
另外提醒一个容易踩的坑:题解的关键点解析中明确写道——“塞入 null 的时候,判断一下当前队列是否为空,不然会无限循环”。
层次遍历的直接变体是锯齿形层次遍历(103. 二叉树的锯齿形层次遍历):遍历过程与 102 完全相同,只是奇数层(从 0 计)将结果倒序输出,题解中用 isOdd 标志位控制 reverse(),见 103 号题解。
六、双色标记法:用一种写法统一三种 DFS 遍历
垃圾回收算法中存在“三色标记法”,其颜色语义为:
- 白色:尚未访问;
- 灰色:尚未完全访问子节点;
- 黑色:子节点已全部访问。
受其启发,仓库笔记发明了双色标记法(两个状态足够),用同一套框架解决前、中、后三种 DFS 遍历:
- 用颜色标记节点状态:新节点为白色(
WHITE = 0),已访问节点为灰色(GRAY = 1); - 遇到白色节点:将其标记为灰色,然后依次压入栈的是
右子节点、自身(灰色)、左子节点; - 遇到灰色节点:输出它的值。
原文档给出的中序遍历实现:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
# 白色:压入 右(白) -> 自身(灰) -> 左(白)
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
前序、后序遍历只需调整三个元素压栈的顺序(即调整 右/自身/左 的相对顺序)即可得到,这就是“统一三种遍历”的具体含义。中文版笔记进一步点出了其本质(thinkings/binary-tree-traversal.md):WHITE 对应递归中“第一次进入节点”的过程,GRAY 对应“从叶子节点返回”的过程,因此这种迭代写法最接近递归的本质,便于记忆和书写;代价是线性额外空间,但由于递归栈开销的常数项更大,实际差异有限——双色迭代法是一种用迭代模拟递归的写法,比普通迭代写法简单得多。
七、Morris 遍历:O(1) 空间的遍历
还有一种既不递归、也不用栈的遍历方式:Morris 遍历。
先更正一个细节:英文版原文写作“time complexity is O(1)”,这与中文版“从而在 空间完成这个过程”(thinkings/binary-tree-traversal.md)相互对照可以判断,正确表述应为时间复杂度 O(n)、空间复杂度 O(1)——每个节点最多被访问两次、每条边最多被走过两次,因此时间是线性的;空间上只用了常量个指针。原文档给出的 Python 实现如下:
def MorrisTraversal(root):
curr = root
while curr:
# If left child is null, print the
# current node data. And, update
# the current pointer to right child.
if curr.left is None:
print(curr.data, end= " ")
curr = curr.right
else:
# Find the inorder predecessor
prev = curr.left
while prev.right is not None and prev.right is not curr:
prev = prev.right
# If the right child of inorder
# predecessor already points to
# the current node, update the
# current with it's right child
if prev.right is curr:
prev.right = None
curr = curr.right
# else If right child doesn't point
# to the current node, then print this
# node's data and update the right child
# pointer with the current node and update
# the current with it's left child
else:
print (curr.data, end=" ")
prev.right = curr
curr = curr.left
其原理可以这样理解:当需要访问某节点 curr 的右子树时,先找到其左子树中的中序前驱(左子树中最右的节点)。若前驱的 right 尚未指向 curr,说明左子树还没走完,先“打一条临时线索”(prev.right = curr)再进入左子树;若已指向 curr,说明左子树已遍历完毕,拆除线索(恢复 prev.right = None)再进入右子树。整个算法通过对树做 O(n) 次可逆的临时修改换取了 O(1) 空间。
仓库的总结是:如果题目要求 O(1) 空间遍历二叉树,就要想到 Morris 遍历。该算法在刷题中考察频率不高,作为了解即可;它同样存在一个副作用——会临时修改树结构,因此不适用于不允许修改输入树的场景。
八、选型建议与相关题目
结合本仓库的专题脉络(thinkings/binary-tree-traversal.md 与 树专题),可以归纳如下选型策略:
| 场景 | 推荐方案 | 空间复杂度 |
|---|---|---|
| 常规遍历 / 数据规模不大 | 递归(DFS) | O(h),h 为树高 |
| 需要迭代且要“统一三种遍历” | 双色标记法 | O(n) |
| 前序 / 中序 / 后序的常规迭代 | 显式栈 | O(n) |
| 层序、锯齿层序、按层处理 | BFS + null 标记位(或记录层长度) |
O(n) |
| 题目明确要求 O(1) 空间 | Morris 遍历 | O(1) |
| 需要实现“迭代器”(每次调用输出一个值) | 文中介绍的显式栈迭代方式,把状态保存在栈中即可 | O(h) |
仓库中与本专题强相关的题目文件,可作为练习序列:
- 144. 二叉树的前序遍历
- 94. 二叉树的中序遍历
- 145. 二叉树的后序遍历
- 102. 二叉树的层序遍历
- 103. 二叉树的锯齿形层次遍历
- 104. 二叉树的最大深度
- 230. 二叉搜索树中第K小的元素
- 98. 验证二叉搜索树
- 301. 删除无效的括号(BFS 应用)
- 609. 在系统中查找重复的文件(DFS 应用)
最后回到开篇的那句话:前中后三序遍历之间变的只是根节点的位置,左右顺序永远是先左后右;而“自上而下递归 + 自底向上用栈”的视角,是把这些差异收敛到同一套框架里的钥匙。掌握了二叉树的遍历,再面对多叉树、森林或带权树时,需要补充的只是孩子节点的组织方式,而遍历的思想可以完全复用。


