概述
基本概念
深度优先遍历（Depth-First Search, DFS）和广度优先遍历（Breadth-First Search, BFS）是两种常见的遍历或搜索树或图的算法。
深度优先遍历（DFS）
深度优先遍历首先深入到可能的最深层次，然后回溯到之前的节点以探索未访问的分支。在二叉树中，DFS可以通过递归或栈来实现。DFS有三种变体：
- 前序遍历（Pre-order）：先访问根节点，然后遍历左子树，最后遍历右子树。
- 中序遍历（In-order）：先遍历左子树，然后访问根节点，最后遍历右子树。
- 后序遍历（Post-order）：先遍历左子树，然后遍历右子树，最后访问根节点。
广度优先遍历（BFS）
广度优先遍历从根节点开始，逐层访问节点。在二叉树中，BFS通常使用队列来实现。BFS首先访问根节点，然后访问根节点的所有直接子节点，接着访问这些子节点的子节点，依此类推，直到所有节点都被访问。
二叉树的DFS和BFS示例
假设我们有以下二叉树：
A
/ \
B C
/ \ \
D E F
DFS（前序遍历）的结果：A B D E C F
DFS（中序遍历）的结果：D B E A C F
DFS（后序遍历）的结果：D E B F C A
BFS的结果：A B C D E F
在实际应用中，DFS和BFS可以根据问题的不同而有不同的用途。例如，DFS通常用于求解路径问题、拓扑排序和连通性问题，而BFS通常用于寻找最短路径、迷宫问题和最近的邻居搜索。
BFS 不是层次遍历
而 BFS 适合求最短距离，这个和层次遍历是不一样的，很多人搞混。这里强调一下，层次遍历和 BFS 是完全不一样的东西。
层次遍历就是一层层遍历树，按照树的层次顺序进行访问。
BFS 的核心在于求最短问题时候可以提前终止，这才是它的核心价值，层次遍历是一种不需要提前终止的 BFS 的副产物。这个提前终止不同于 DFS 的剪枝的提前终止，而是找到最近目标的提前终止。比如我要找距离最近的目标节点，BFS 找到目标节点就可以直接返回。而 DFS 要穷举所有可能才能找到最近的，这才是 BFS 的核心价值。实际上，我们也可以使用 DFS 实现层次遍历的效果，借助于递归，代码甚至会更简单。
代码实现
在JavaScript中，我们可以使用递归或迭代的方式来编写二叉树的前序、中序和后序遍历算法。下面我将分别展示这三种遍历方式的递归和迭代实现。
首先，我们需要定义一个二叉树的节点类：
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
然后，我们可以实现遍历算法：
前序遍历
function preorderTraversal(root) {
let result = [];
function traverse(node) {
if (node === null) return;
result.push(node.val); // 访问根节点
traverse(node.left); // 遍历左子树
traverse(node.right); // 遍历右子树
}
traverse(root);
return result;
}
中序遍历
function inorderTraversal(root) {
let result = [];
function traverse(node) {
if (node === null) return;
traverse(node.left); // 遍历左子树
result.push(node.val); // 访问根节点
traverse(node.right); // 遍历右子树
}
traverse(root);
return result;
}
后序遍历
function postorderTraversal(root) {
let result = [];
function traverse(node) {
if (node === null) return;
traverse(node.left); // 遍历左子树
traverse(node.right); // 遍历右子树
result.push(node.val); // 访问根节点
}
traverse(root);
return result;
}
迭代实现
双色标记法来统一前中后序遍历，下面是中序遍历其他的以此类推。
中序遍历
var inorderTraversal = function(root) {
const WHITE = 0, GRAY = 1; // 定义两种颜色，WHITE表示未访问，GRAY表示已访问
const res = []; // 存储遍历结果
const stack = [[WHITE, root]]; // 初始化栈，推入根节点和颜色标记
while (stack.length > 0) {
const [color, node] = stack.pop(); // 弹出栈顶元素和颜色标记
if (!node) continue; // 如果节点为空，则继续下一次循环
if (color === WHITE) {
// 如果节点颜色为WHITE，表示第一次访问
stack.push([WHITE, node.right]); // 先推入右子节点（WHITE）
stack.push([GRAY, node]); // 推入当前节点（GRAY）
stack.push([WHITE, node.left]); // 再推入左子节点（WHITE）
} else {
// 如果节点颜色为GRAY，表示第二次访问
res.push(node.val); // 将节点值加入结果数组
}
}
return res; // 返回遍历结果
};
层次遍历
function levelOrder(root) {
let result = [];
if (root === null) return result;
let queue = [root]; // 初始化队列，将根节点入队
while (queue.length > 0) {
let level = []; // 存储当前层的节点值
let levelSize = queue.length; // 当前层的节点数量
for (let i = 0; i < levelSize; i++) {
let node = queue.shift(); // 出队当前节点
level.push(node.val); // 将节点值加入当前层的结果数组
// 将非空的左子节点和右子节点入队
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
result.push(level); // 将当前层的结果数组加入最终结果
}
return result;
}
在这个实现中，我们使用了一个数组queue来模拟队列。
- 首先，我们将根节点入队。
- 然后，我们进入一个循环，每次循环中我们处理当前层的所有节点。
- 我们使用一个额外的数组
level来存储当前层的节点值，并使用levelSize来记录当前层的节点数量。 - 在循环中，我们逐个出队节点，并将它们的值加入
level数组，同时将它们的非空子节点入队。 - 当当前层的所有节点都被处理完后，我们将
level数组加入最终结果result中。
- 我们使用一个额外的数组
- 循环继续，直到队列为空，这时所有层的节点都已经被遍历完毕。