题目:二叉树层序遍历

无论去与住，俱是梦中人。

二叉树层序遍历

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

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

代码实现

1. 分层

var levelOrder = function (root) {
  let arr = [];
  let i = 0;
  let end = 0;
  while (end < root.length) {
    let start = end;
    end = Math.pow(2, i) + end;
    i++;
    let temArr = [];
    for (let j = start; j < end; j++) {
      if (root[j]) {
        temArr.push(root[j]);
      }
    }
    arr.push(temArr);
  }
  return arr;
};

2. 队列 BFS(广度优先搜索)

var levelOrder = function(root) {
    const ret = [];
    if (!root) {
        return ret;
    }

    const q = [];
    q.push(root);
    while (q.length !== 0) {
        const currentLevelSize = q.length;
        ret.push([]);
        for (let i = 1; i <= currentLevelSize; ++i) {
            const node = q.shift();
            ret[ret.length - 1].push(node.val);
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
    }
    return ret;
};