一起走进遍历二叉树的奇妙之旅：递归、迭代与统一迭代法全详解
一起走进遍历二叉树的奇妙之旅：递归、迭代与统一迭代法全详解
二叉树的遍历是计算机科学中的一个基础且重要的概念，广泛应用于数据结构和算法中。本文将系统地介绍二叉树的深度优先遍历（DFS）和广度优先遍历（BFS），包括前序遍历、中序遍历、后序遍历和层序遍历，并提供递归和迭代两种实现方式。此外，本文还将介绍统一迭代法，通过空指针标记法实现三种遍历方式的统一代码风格。
”生活的底片从来不是遥远的白日梦，而是热爱生活的自己 “
二叉树的遍历
二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方式分为两大类：深度优先遍历（DFS） 和 广度优先遍历（BFS）。以下是详细的遍历方式及其实现方法：
1. 深度优先遍历（DFS）
深度优先遍历是从根节点出发，沿着一条路径尽可能深地访问节点，直到到达叶子节点，然后回溯到上一个节点继续遍历。DFS 有三种常见方式：
(1) 前序遍历（Preorder Traversal）
顺序：根节点 → 左子树 → 右子树
应用场景：复制树、表达式树的前缀表示。
递归实现
function preorder(root) {
if (!root) return;
console.log(root.val); // 访问根节点
preorder(root.left); // 遍历左子树
preorder(root.right); // 遍历右子树
}
(2) 中序遍历（Inorder Traversal）
顺序：左子树 → 根节点 → 右子树
应用场景：二叉搜索树的中序遍历结果是有序的。
递归实现
function inorder(root) {
if (!root) return;
inorder(root.left); // 遍历左子树
console.log(root.val); // 访问根节点
inorder(root.right); // 遍历右子树
}
(3) 后序遍历（Postorder Traversal）
顺序：左子树 → 右子树 → 根节点
应用场景：删除树、表达式树的后缀表示。
递归实现
function postorder(root) {
if (!root) return;
postorder(root.left); // 遍历左子树
postorder(root.right); // 遍历右子树
console.log(root.val); // 访问根节点
}
2. 广度优先遍历（BFS）
广度优先遍历是按层次从上到下、从左到右访问节点。通常使用队列实现。
层序遍历（Level Order Traversal）
顺序：从上到下、从左到右逐层访问节点。
应用场景：求树的深度、按层打印节点。
队列实现
function levelOrder(root) {
if (!root) return;
const queue = [root];
while (queue.length) {
const node = queue.shift();
console.log(node.val); // 访问当前节点
if (node.left) queue.push(node.left); // 左子节点入队
if (node.right) queue.push(node.right); // 右子节点入队
}
}
按层输出
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
3. 遍历方式对比
遍历方式 | 顺序 | 应用场景 | 实现方式 |
|---|---|---|---|
前序遍历 | 根 → 左 → 右 | 复制树、前缀表达式 | 递归、栈 |
中序遍历 | 左 → 根 → 右 | 二叉搜索树的有序输出 | 递归、栈 |
后序遍历 | 左 → 右 → 根 | 删除树、后缀表达式 | 递归、栈 |
层序遍历 | 从上到下、从左到右 | 求树的深度、按层打印节点 | 队列 |
二叉树的递归遍历
- 144.二叉树的前序遍历(opens new window)
- 145.二叉树的后序遍历(opens new window)
- 94.二叉树的中序遍历
在这部分的题目中，主要是想要锻炼我们对二叉树遍历的理解。
各个遍历的规律是：前序遍历：中左右、中序遍历：左中右、后序遍历：左右中；
我们采用递归法来分别实现，代码如下：
前序遍历
var preorderTraversal = function(root) {
return root
? [
// 前序遍历：中左右
root.val,
// 递归左子树
...preorderTraversal(root.left),
// 递归右子树
...preorderTraversal(root.right),
]
: [];
};
中序遍历
var inorderTraversal = function(root) {
return root
? [
// 中序遍历：左中右
// 递归左子树
...inorderTraversal(root.left),
root.val,
// 递归右子树
...inorderTraversal(root.right),
]
: [];
};
后序遍历
var postorderTraversal = function(root) {
return root
? [
// 递归左子树
...postorderTraversal(root.left),
// 递归右子树
...postorderTraversal(root.right),
root.val,
]
: [];
};
二叉树的迭代遍历
为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
我们在栈与队列：匹配问题都是栈的强项 (opens new window)中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。
迭代法就是借用栈的思想来实现二叉树的遍历，但是不同的遍历有不一样。
前序遍历
前序遍历:
// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
var preorderTraversal = function(root, res = []) {
if(!root) return res;
const stack = [root];
let cur = null;
while(stack.length) {
cur = stack.pop();
res.push(cur.val);
cur.right && stack.push(cur.right);
cur.left && stack.push(cur.left);
}
return res;
};
因为我们要满足出栈是是中左右的顺序，根据栈先进后出的特性，我们入栈的顺序应该是右左。
中序遍历
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
借用一下代码随想录的动画来解释：
中序遍历:
// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右
var inorderTraversal = function(root, res = []) {
const stack = [];
let cur = root;
while(stack.length || cur) {
if(cur) {
stack.push(cur);
// 左
cur = cur.left;
} else {
// --> 弹出 中
cur = stack.pop();
res.push(cur.val);
// 右
cur = cur.right;
}
};
return res;
};
当访问到左边的最底部时，即if（cur）时，我们开始处理节点，往上逐步处理。
后序遍历
再来看后序遍历，先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
var postorderTraversal = function(root, res = []) {
if (!root) return res;
const stack = [root];
let cur = null;
do {
cur = stack.pop();
res.push(cur.val);
cur.left && stack.push(cur.left);
cur.right && stack.push(cur.right);
} while(stack.length);
return res.reverse();
};
只用反转一下前序遍历的顺序就好啦。
二叉树的统一迭代法
我们发现迭代法实现的先中后序，其实风格也不是那么统一，除了先序和后序，有关联，中序完全就是另一个风格了，一会用栈遍历，一会又用指针来遍历。
其实针对三种遍历方式，使用迭代法是可以写出统一风格的代码！
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢？
方法一：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法可以叫做
空指针标记法
。方法二：加一个
boolean
值跟随每个节点，
false
(默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次，
true
表示该节点的位次之前已经安排过了，可以收割节点了。 这种方法可以叫做
boolean 标记法
，样例代码见下文
C++ 和 Python 的 boolean 标记法
。 这种方法更容易理解，在面试中更容易写出来。
我们的做法是，我们讲访问的节点直接加入栈中，但是如果是要处理的节点我们就在后面放入一个空节点。然后统一收割节点。
然后不同的遍历方式，只需要改变代码的先后就行了。
前序遍历
// 前序遍历：中左右
// 压栈顺序：右左中
var preorderTraversal = function(root, res = []) {
const stack = [];
if (root) stack.push(root);
while(stack.length) {
const node = stack.pop();
if(!node) {
res.push(stack.pop().val);
continue;
}
if (node.right) stack.push(node.right); // 右
if (node.left) stack.push(node.left); // 左
stack.push(node); // 中
stack.push(null);
};
return res;
};
中序遍历
// 中序遍历：左中右
// 压栈顺序：右中左
var inorderTraversal = function(root, res = []) {
const stack = [];
if (root) stack.push(root);
while(stack.length) {
const node = stack.pop();
if(!node) {
res.push(stack.pop().val);
continue;
}
if (node.right) stack.push(node.right); // 右
stack.push(node); // 中
stack.push(null);
if (node.left) stack.push(node.left); // 左
};
return res;
};
后序遍历
// 后续遍历：左右中
// 压栈顺序：中右左
var postorderTraversal = function(root, res = []) {
const stack = [];
if (root) stack.push(root);
while(stack.length) {
const node = stack.pop();
if(!node) {
res.push(stack.pop().val);
continue;
}
stack.push(node); // 中
stack.push(null);
if (node.right) stack.push(node.right); // 右
if (node.left) stack.push(node.left); // 左
};
return res;
};
本文原文来自CSDN