复盘 · LC 102 二叉树的层序遍历

题目

• 题号：LeetCode 102
• 名称：二叉树的层序遍历（Binary Tree Level Order Traversal）
• 难度：Medium
• 链接：leetcode.cn/problems/binary-tree-level-order-traversal
• 今日代码：102-二叉树的层序遍历/index.js

题意

自顶向下，按层返回节点值：List[List[int]]，同一层从左到右。

• 空树返回 []。
• 一层一个子数组。

涉及算法

标签	一句话
BFS / 队列	先进先出；按层收集
分层技巧	经典：每层开始记 size = queue.length，循环 size 次；或节点带 depth

教程对照：16 · 二叉树遍历、18 · BFS 层序与 BST、11 · 队列与层序思想。

评价我的解法

用「节点 + depth」入队，depth 变大就新开一层——能做对。

我的代码（摘自 102-二叉树的层序遍历/index.js）：

var levelOrder = function (root) {
  if (!root) {
    return [];
  }
  const nodeArr = [
    {
      node: root,
      depth: 1,
    },
  ];
  const resArr = [];
  let curDepth = 0;
  while (nodeArr.length > 0) {
    const nodeObj = nodeArr.shift();
    const node = nodeObj.node;
    const depth = nodeObj.depth;
    if (depth > curDepth) {
      resArr.push([node.val]);
    } else {
      resArr[resArr.length - 1].push(node.val);
    }
    curDepth = depth;
    if (node.left) {
      nodeArr.push({
        node: node.left,
        depth: depth + 1,
      });
    }
    if (node.right) {
      nodeArr.push({
        node: node.right,
        depth: depth + 1,
      });
    }
  }
  return resArr;
};

评价：

1. 结果正确：BFS 顺序对；用 depth 切层逻辑成立。
2. 偏重：每个节点包一层对象；面试更常写「按层 size」——不需要 depth 字段，空间与口述都更轻。
3. shift 队列：JS 数组 shift 是 O(n)，整题近似 O(n²) 最坏；题量小能过，严谨可写头指针或用真正的队列。树题面试通常仍接受数组模拟。
4. 复杂度（逻辑）：访问每个节点一次 → O(n)；额外队列 O(n)。

小结：层序直觉有了；建议默写一版「for (let i = 0; i < size; i++)」模板，和教程 18 对齐。

最佳题解

按层 size 模板：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  while (q.length) {
    const size = q.length;
    const level = [];
    for (let i = 0; i < size; i++) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
};

• 时间 O(n)（忽略 shift 实现代价），空间 O(n)。
• 为何更优：分层语义直接落在循环结构上，少带 depth，扩展到「只看右视图 / 锯齿层序」也更顺。

关联题目

题	为何相关
107. 二叉树的层序遍历 II	同一 BFS，结果倒序或 unshift
199. 二叉树的右视图	每层最后一个
429. N 叉树的层序遍历	同一 size 模板

一句话带走

层序：队列 + 每层先记 size，循环 size 次——比人手搓 depth 更省事。