二叉树层序遍历

问题

实现二叉树的层序遍历，按层从上到下、从左到右输出节点值。

    3
   / \
  9  20
    /  \
   15   7

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

解答

定义二叉树节点

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

BFS 层序遍历

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root]; // 用数组模拟队列

  while (queue.length > 0) {
    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
//    / \
//   9  20
//     /  \
//    15   7
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(levelOrder(root));
// 输出: [[3], [9, 20], [15, 7]]

变体：返回一维数组

function levelOrderFlat(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

console.log(levelOrderFlat(root));
// 输出: [3, 9, 20, 15, 7]

关键点

• 使用队列（先进先出）存储待访问节点
• 记录每层节点数 levelSize，用于区分层级
• 时间复杂度 O(n)，每个节点访问一次
• 空间复杂度 O(n)，最坏情况队列存储一整层节点
• BFS 天然适合层序遍历，DFS 需要额外记录深度