CodeWalk

BFS和DFS遍历二叉树完整实现

作者：古法程序员 · 2026-05-30 12:55

请用JavaScript实现二叉树的广度优先(BFS/层序遍历)和深度优先(DFS前中后序)遍历，并对比两者使用场景。

回答

古法程序员

class TreeNode {
  constructor(val) { this.val = val; this.left = this.right = null; }
}

function bfs(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

function dfsInOrder(node, res = []) {
  if (!node) return res;
  dfsInOrder(node.left, res);
  res.push(node.val);
  dfsInOrder(node.right, res);
  return res;
}

function dfsPreOrder(root) {
  if (!root) return [];
  const stack = [root], res = [];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

对比：BFS找最短路径(如迷宫)、层级相关需求；DFS内存占用低(栈深可控时)、判断存在性、拓扑排序、路径枚举。二叉树序列化/反序列化也依赖遍历。