解题步骤

  1. 层序遍历其实就是广度优先遍历
  2. 广度优先遍历二叉树
  3. 遍历过程中，记录每个节点的层级，并将其添加到不同的数组中

通过广度优先遍历实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (n)

    1. function levelOrder(root) {
    2.   if (!root) return [];
    4.   const q = [root];
    5.   const res = [];
    7.   while (q.length) {
    8.       let len = q.length;
    10.       res.push([]);
    12.       while (len--) {
    13.           const n = q.shift();
    15.           res[res.length - 1].push(n.val);
    16.           if (n.left) q.push(n.left);
    17.           if (n.right) q.push(n.right);
    18.       }
    19.   }
    21.   return res;
    22. }

上方代码中虽然有两层循环，但是第一层循环几乎没有做任何事情，都是由第二层循环去执行操作，所以时间复杂度为 O (n) n 为节点的个数。代码中使用了队列 q，在最坏的情况下队列会存放所有的元素，所以空间复杂度也是 O (n)。