跳到主要内容

二叉树的层序遍历

问题​

给你二叉树的根节点 root，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

示例：

输入：root = [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7

输出：[[3],[9,20],[15,7]]

来源：LeetCode 102. 二叉树的层序遍历

前置知识​

TreeNode.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number = 0, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

答案​

方法一：BFS 队列（推荐）​

核心思路：使用队列，每次处理一整层。关键在于"分层"——处理前先记录当前队列长度，这个长度就是这一层的节点数。

levelOrder.ts
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点数
    const level: number[] = [];

    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;
}

图解过程：

        3
       / \
      9  20
        /  \
       15   7

初始：queue = [3]

第1层：levelSize = 1
  取出 3，加入其子节点 9, 20
  level = [3]
  queue = [9, 20]

第2层：levelSize = 2
  取出 9（无子节点），取出 20（子节点 15, 7）
  level = [9, 20]
  queue = [15, 7]

第3层：levelSize = 2
  取出 15, 7（都无子节点）
  level = [15, 7]
  queue = []

结果：[[3], [9, 20], [15, 7]]
复杂度分析
  • 时间复杂度：O(n)O(n) — 每个节点访问一次
  • 空间复杂度：O(n)O(n) — 队列最多存一层的节点（最宽的一层）

方法二：DFS 递归​

在 DFS 过程中传入层级信息：

levelOrderDFS.ts
function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];

  function dfs(node: TreeNode | null, depth: number): void {
    if (!node) return;

    // 如果当前层还没有数组，创建一个
    if (result.length === depth) {
      result.push([]);
    }

    result[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }

  dfs(root, 0);
  return result;
}
何时用 BFS vs DFS？
  • BFS：更直观的"按层处理"，适合需要层级信息的场景
  • DFS：代码更简洁，但需要额外传递 depth 参数

面试中两种都要会，通常先写 BFS，再被问到时补充 DFS。

方法三：迭代优化（避免 shift 的开销）​

Array.shift() 是 O(n)O(n) 操作，可以用指针代替：

levelOrderOptimized.ts
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  let currentLevel: TreeNode[] = [root];

  while (currentLevel.length > 0) {
    const level: number[] = [];
    const nextLevel: TreeNode[] = [];

    for (const node of currentLevel) {
      level.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    result.push(level);
    currentLevel = nextLevel;
  }

  return result;
}
性能更优

使用两个数组交替的方式避免了 shift() 操作，实际运行速度更快。

常见面试追问​

Q1: 如何实现锯齿形层序遍历？(LeetCode 103)​

答案：偶数层反转：

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];

    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(leftToRight ? level : level.reverse());
    leftToRight = !leftToRight;
  }

  return result;
}

Q2: 如何获取二叉树的右视图？(LeetCode 199)​

答案：层序遍历的每一层取最后一个元素：

function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (i === levelSize - 1) result.push(node.val); // 每层最后一个
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return result;
}

Q3: 层序遍历在前端有什么应用？​

答案：

  • DOM 树遍历：按层遍历 DOM 节点
  • React 组件树：DevTools 按层展示组件结构
  • 文件树展示：文件管理器的树形展开
  • 组织架构图：按层级展示
// DOM 层序遍历示例
function traverseDOM(root: HTMLElement): HTMLElement[][] {
  const result: HTMLElement[][] = [];
  const queue: HTMLElement[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: HTMLElement[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node);
      queue.push(...Array.from(node.children) as HTMLElement[]);
    }

    result.push(level);
  }

  return result;
}

相关链接​