二叉树层次遍历

问题

二叉树的层次遍历是指按照从上到下、从左到右的顺序逐层访问二叉树的所有节点。这是一种广度优先遍历（BFS）的应用，需要将每一层的节点按顺序输出，通常以二维数组的形式返回结果，每个子数组代表树的一层。

解答

// 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

/**
 * 二叉树层次遍历 - 使用队列实现
 * @param {TreeNode} root - 二叉树根节点
 * @return {number[][]} - 层次遍历结果，二维数组
 */
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;
}

/**
 * 二叉树层次遍历 - 递归实现
 * @param {TreeNode} root - 二叉树根节点
 * @return {number[][]} - 层次遍历结果
 */
function levelOrderRecursive(root) {
  const result = [];
  
  function traverse(node, level) {
    if (!node) return;
    
    // 如果当前层还没有数组，创建一个
    if (result.length === level) {
      result.push([]);
    }
    
    // 将当前节点值加入对应层
    result[level].push(node.val);
    
    // 递归遍历左右子树，层级加1
    traverse(node.left, level + 1);
    traverse(node.right, level + 1);
  }
  
  traverse(root, 0);
  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]]

// 使用递归方法
console.log(levelOrderRecursive(root));
// 输出: [[3], [9, 20], [15, 7]]

// 测试空树
console.log(levelOrder(null));
// 输出: []

// 测试单节点树
const singleNode = new TreeNode(1);
console.log(levelOrder(singleNode));
// 输出: [[1]]

// 测试完全二叉树
//       1
//      / \
//     2   3
//    / \
//   4   5
const completeTree = new TreeNode(1);
completeTree.left = new TreeNode(2);
completeTree.right = new TreeNode(3);
completeTree.left.left = new TreeNode(4);
completeTree.left.right = new TreeNode(5);

console.log(levelOrder(completeTree));
// 输出: [[1], [2, 3], [4, 5]]

关键点

• 队列实现（推荐）：使用队列数据结构实现 BFS，先进先出的特性天然适合层次遍历
• 层级控制：通过记录每层的节点数量（levelSize），确保每次只处理当前层的节点
• 节点入队顺序：先左后右地将子节点加入队列，保证同层节点从左到右的顺序
• 递归实现：通过传递层级参数，将节点值放入对应层的数组中，代码更简洁但空间复杂度略高
• 边界处理：需要处理空树、单节点等特殊情况
• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(n)，队列最多存储最宽一层的节点数量，最坏情况下为 n/2