leetcode 题解仓库中的二叉树遍历算法详解:DFS、BFS、双色标记法与 Morris 遍历
leetcode 题解仓库中的二叉树遍历算法详解:DFS、BFS、双色标记法与 Morris 遍历
二叉树遍历是树形数据结构最基础也最经典的算法族,在 leetcode 题解仓库 中,它被总结为一个独立专题(thinkings/binary-tree-traversal.md),并贯穿前序、中序、后序三种 DFS 遍历与层次遍历(BFS)四大主线。读完本篇,你将掌握四种遍历的完整迭代实现思路、统一的「自顶向下 + 自底向上」框架、用双色标记法统一三种遍历的技巧,以及 O(1) 空间 Morris 遍历的原理,并能把遍历能力迁移到 BST 验证、第 K 小元素等高频题型上。
一、概述:DFS 与 BFS 两条主线
二叉树作为基础数据结构,遍历算法作为基础算法,两者结合是刷题中的经典组合:很多题目会直接或间接考察树的遍历——比如「找到树中满足条件的节点」这类题,本质上要求你先完成一次完整遍历。
仓库中的总结可以概括为三条主线:
- DFS 三条路线:前序(根-左-右)、中序(左-根-右)、后序(左-右-根)。前中后序属于深度优先遍历,它们变化的只是根节点的输出位置,左右子树的访问顺序永远是先左后右。
- 层次遍历:即 BFS,也可以理解为「没有提前终止的 BFS」——用队列即可实现,BFS 比 DFS 更适合表达层序语义。
- 两个关键点:DFS 可以用栈来简化操作;树本身是递归的数据结构,因此「递归」和「栈」是 DFS 的两个关键要素。这一点在仓库的 深度优先遍历专题 中也有呼应:DFS 中的 stack 可以理解为自实现的栈,也可以理解为语言的调用栈。
DFS 与 BFS 各自都有典型应用,例如仓库题解中提到的 LeetCode 301 号问题(去除重复节点,基于栈的 DFS)与 609 号问题(基于 BFS 的重复子树识别),可以体会两种遍历的适用差异。
二、前序遍历(根-左-右)
对应题目:144.binary-tree-preorder-traversal。
前序遍历的顺序是 根-左-右,因为根节点最先访问,迭代实现相对简单。核心思路(摘自仓库专题):
- 先将根节点入栈;
- 出栈一个元素,将其右节点和左节点依次入栈(注意入栈顺序是右先左后,这样左节点才能先出栈);
- 重复步骤 2。
仓库中给出的 JavaScript 迭代实现完整保留了「先处理当前节点、再压入子节点」的结构:
var preorderTraversal = function (root) {
if (!root) return [];
const ret = [];
const stack = [root];
let t = stack.pop();
while (t) {
if (t.right) {
stack.push(t.right);
}
if (t.left) {
stack.push(t.left);
}
ret.push(t.val);
t = stack.pop();
}
return ret;
};
(代码取自 problems/144.binary-tree-preorder-traversal.md,时间复杂度 O(N),空间复杂度 O(N))
此外,仓库还指出了一种「宏观视角」的写法:前序遍历整体表现为自顶向下依次访问左侧链,然后自底向上依次访问右侧链。对应到代码上就是:从上向下用 while 循环不断压入左链并输出,从下向上借助栈弹出节点转向右子树。该仓库中 C++ 版本的迭代实现正是这种写法:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
vector<TreeNode*> s;
while (root != NULL || !s.empty()) {
while (root != NULL) { // 自顶向下:一路压左链并输出
v.push_back(root->val);
s.push_back(root);
root = root->left;
}
root = s.back()->right; // 自底向上:弹出后转向右子树
s.pop_back();
}
return v;
}
};
这种写法的重要价值在于:它可以统一三种遍历的思路——前序、中序、后序只需要微调「输出时机」(见第三节)。
三、中序遍历(左-根-右)
对应题目:94.binary-tree-inorder-traversal。
中序遍历的顺序是 左-根-右,根节点不是先输出,迭代实现因此比前序略复杂。仓库给出的步骤:
- 根节点入栈;
- 判断有没有左节点,如果有则继续入栈,直到叶子节点——此时栈中保存的就是所有左链节点加上根节点;
- 出栈一个节点(输出它),判断有没有右节点,有则入栈,回到步骤 2。
仓库中的多语言迭代实现,以 JavaScript 为例:
var inorderTraversal = function (root) {
const res = [];
const stk = [];
while (root || stk.length) {
while (root) { // 一路把左链压栈
stk.push(root);
root = root.left;
}
root = stk.pop(); // 弹出即访问
res.push(root.val);
root = root.right; // 转向右子树
}
return res;
};
(完整 JS/C++/Python/Java 四种语言实现见 problems/94.binary-tree-inorder-traversal.md)
BST 性质:中序遍历一棵二叉查找树(BST)的结果是一个有序数组。仓库中两个典型应用印证了这一点:
- 230.kth-smallest-element-in-a-bst:沿中序遍历数到第 k 个节点直接返回即可,题解中给出了「计数到 k 提前终止」的迭代实现,还有基于子树节点计数剪枝的第二解法;
- 98.validate-binary-search-tree:中序遍历过程中维护前驱节点
pre,一旦发现cur.val <= pre.val即判定不是 BST,避免了把整棵树结果存成数组。
这两道题的前置知识都标注为「中序遍历」,与遍历专题直接对应。
四、后序遍历(左-右-根)
对应题目:145.binary-tree-postorder-traversal。
后序遍历的顺序是 左-右-根,也是三道经典遍历题中 LeetCode 难度最高的一道(Hard)。难点在于:根节点最后才输出,因此在迭代中不能像前序那样「出栈即输出」。仓库给出的讨巧做法是记录节点状态,满足以下任一条件才出栈输出:
- 当前节点是叶子节点(left 和 right 同时为 null);
- 当前节点的左右子树都已经遍历过(用一个变量记录上一个访问的节点即可,最坏情况才需要记录每个节点的访问状况,那样空间复杂度是 O(n),而只记录「上一个出栈元素」即可做到 O(1) 额外状态)。
仓库中的 JavaScript 实现完整体现了这个判断:
var postorderTraversal = function (root) {
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++ 版本见 problems/145.binary-tree-postorder-traversal.md;C++ 版本用 prev 指针判断右子树是否已访问,同样只需 O(1) 额外状态)
五、层次遍历(BFS)
对应题目:102.binary-tree-level-order-traversal。
层次遍历的关键点在于如何记录每一层是否遍历完成。仓库给出的做法是「入队一个特殊标识位(null)表示本层结束」:
- 根节点入队列,同时入队一个特殊标识位(null);
- 出队列;
- 如果出队的是 null,代表本层已经结束:再次判断队列是否为空,不为空则继续入队一个 null,否则说明遍历完成,什么都不做(注意这里必须判空,否则会无限循环);
- 如果不为 null,说明本层还没完,将其左右子节点依次入队列。
仓库中的 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;
};
(代码见 problems/102.binary-tree-level-order-traversal.md,时间复杂度 O(N),空间复杂度 O(N))
仓库题解同时提供了两种替代方案,值得注意:
- 不用 null 标识位:在 while 循环开始时保存当前队列长度
sz,每次只处理sz个节点,即天然完成一层(C++ 迭代版采用此法); - 递归方式:把当前节点、所在 level 以及结果数组传递给递归函数,按 level 把节点值追加到结果数组对应层(C++ 递归版与 Python 递归版采用此法)。
六、双色标记法:一种统一三种遍历的写法
仓库专题最后介绍了模仿垃圾回收「三色标记法」思想的双色标记法:
- 用颜色标记节点状态:新节点为白色,已访问的节点为灰色;
- 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈(入栈顺序恰好决定了出栈后的处理顺序);
- 如果遇到的节点为灰色,则将节点的值输出。
仓库原文给出的中序遍历 Python 实现:
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
从实现上可以看出:WHITE 表示递归中的「第一次进入」过程,GRAY 表示递归中的「从子树返回」过程,因此这种迭代写法更接近递归的本质。要改成前序或后序遍历,只需要调整「右子节点、自身(GRAY)、左子节点」三者的入栈顺序即可。
仓库对此方法的评述是:写法类似递归形式,便于记忆和书写,缺点是使用了额外的线性内存空间;不过与递归相比,它只是每节点多存一个 0/1 颜色变量,空间复杂度的常数项更小(递归调用栈的单帧开销通常大于一个整型标记)。划重点:双色迭代法是一种用迭代模拟递归的写法,其写法和递归非常相似,要比普通迭代简单得多。
七、Morris 遍历:O(1) 空间的遍历
如果需要 O(1) 额外空间遍历一棵二叉树(既不用递归也不用栈),仓库介绍了 Morris 遍历:利用中序前驱节点的右指针为空这一特点,临时把它指向当前节点建立「线程」(thread),访问完左子树后再沿着线程回来并恢复指针,从而省去栈。仓库给出的 Python 实现(以原稿为准,属于先序输出形态的 Morris 遍历):
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
划重点:Morris 遍历是一种可以在 O(1) 空间遍历二叉树的算法。 仓库同时提示:该算法考察相对少,作为了解即可;另外需要注意它通过临时修改树指针实现,若树不可变或需并发访问则不适用。
八、总结与延伸
- DFS 三个变体(前序/中序/后序)变化的是根节点输出位置,左右子树顺序永远是先左后右;迭代写法围绕「栈」展开,其中「自顶向下走左链 + 自底向上转右子树」的框架可以统一前序与中序,后序则需额外记录上一个访问节点来判断输出时机;
- 层次遍历用队列 + 层末标识位(或层初队列长度)即可实现,本质是不带提前终止的 BFS;
- 双色标记法用「入栈三件套(右、自身、左)」统一三种遍历,是比手写迭代更接近递归本质的记忆方式;Morris 遍历以 O(1) 空间为目标,作为了解即可;
- 如果题目要求实现迭代器(每调用一次输出一个节点值),本文讲的迭代写法(尤其是中序遍历维护左链栈的写法)非常适用,典型如 BST Iterator 类题目;
- 遍历能力是树题的地基:最近公共祖先、锯齿形层序遍历、验证二叉搜索树、最大深度、平衡二叉树、二叉树最大路径和等常见题型,都建立在这四种遍历之上。仓库中对应的题解可参考 124.binary-tree-maximum-path-sum、236.lowest-common-ancestor-of-a-binary-tree、103.binary-tree-zigzag-level-order-traversal、104.maximum-depth-of-binary-tree 等。
掌握二叉树遍历之后,其他更复杂的树形结构(如 N 叉树、Trie、线段树)的遍历方法也不远矣——它们无非是上述 DFS/BFS 框架在「节点子节点个数大于 2」场景下的自然推广。

