定义

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用

数据结构

使用队列进行遍历。
借用队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

队列函数

push()是用来在数组末端添加项
pop()在数组末端移除项

unshift()在数组前端添加项
shift()在移除数组的第一个项（前端）

push(),unshift()在推入多个项时，各个项之间的顺序不变
push(),unshift()将数组的长度+n并返回的是数组的长度
pop(),shift()将数组length-n并返回的是移除的项

自顶向下的层序遍历

var levelOrder = function(root) {
  let res =[];
  let queue =[];
  queue.push(root);
  if(!root)return res;
  while(queue.length!==0){
    let curLevel =[];
    let curLength =queue.length;
    for(let i =0;i<curLength;i++){
      // pop是移除队列末端值，shift是前端值
      const node =queue.shift();
      curLevel.push(node.val);
      node.left&& queue.push(node.left);
      node.right&& queue.push(node.right);
    }
    res.push(curLevel);        
  }
  return res;
};

自底向上的层序遍历

PS：不使用反转，而是用unshift从前插入（JS还真是自由啊、）

var levelOrderBottom = function(root) {
    let res =[];
    let queue =[root];
    if(!root)return res;
    while(queue.length!=0){
        let curLevel =[];
        let curLength =queue.length;
        for(let i =0;i<curLength;i++){
            const node =queue.shift();
            curLevel.push(node.val);
            node.left&& queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        // res.push(curLevel);
        // 从前插入每层遍历，避免反转的多余时间浪费
        res.unshift(curLevel);
    }
    // return res.reverse();
    return res;
};

二叉树的右视图

题意就是遍历存储每层的最后一个。
我是先记录每一层再存最后一个。
大神是直接记录当length=0时，就是每层最后一个值。

var rightSideView = function(root) {
    //二叉树右视图 只需要把每一层最后一个节点存储到res数组
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        // 记录当前层级节点个数
        let length=queue.length;
        while(length--){
            let node=queue.shift();
            //length长度为0的时候表明到了层级最后一个节点
            if(!length){
                res.push(node.val);
            }
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return res;
};

N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
要点：不再是node.left 和 node.right
for(let item of node.children)

var levelOrder = function(root) {
    //每一层可能有2个以上,所以不再使用node.left node.right
    let res=[],queue=[];
    queue.push(root);
    while(queue.length&&root!==null){
        //记录每一层节点个数还是和二叉树一致
        let length=queue.length;
        //存放每层节点 也和二叉树一致
        let curLevel=[];
        while(length--){
            let node = queue.shift();
            curLevel.push(node.val);
            //这里不再是 ndoe.left node.right 而是循坏node.children
           for(let item of node.children){
               item&&queue.push(item);
           }
        }
        res.push(curLevel);
    }
    return res;
};

116.填充每个节点的下一个右侧节点指针

踩坑：注意审题！
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
分析：这道题的含义是让我们填充next，所以不用再定义res数组来输出，系统自动进行层序遍历输出。用res反而报错！
坑2：
shift()、pop()等函数会移除元素的，所以在取出元素后，它的next元素永远是queue[0]。

var connect = function(root) {
    // let res =[];
    let queue =[root];

    while(queue.length&&root){
        let curLength =queue.length;
        for(let i =0;i<curLength;i++){
            const node =queue.shift();
            // res.push(node.val); 不用存储，直接输入root
            // if(i==curLength-1){
            //     // res.push("#");
            //     node.next =null;
            // }else{
            //     node.next =queue[0]; //shift会移除元素，所以next一直是queue[0]
            // }
            // 所以简洁写法如下：
            if(i<curLength-1){
                node.next =queue[0];
            }
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

104.二叉树的最大深度

思路：求层序遍历有多少层
模板做法即可。

一行代码递归法：

var maxdepth = function(root) {
    if (!root) return root
    return 1 + math.max(maxdepth(root.left), maxdepth(root.right))
};

111. 二叉树的最小深度

坑：空树时为0，非空时最小为1.所以要先判断空树。

var minDepth = function(root) {
    // 层序遍历，找到没有左右子节点时停止
    let queue =[root];
    let minCount =1;
    if(!root){
        return 0;
    }
    while(queue.length){
        let curLength =queue.length;
        while(curLength--){
            const node =queue.shift();
            if(!node.left&&!node.right){
                return minCount;
            }else{
                node.left&&queue.push(node.left);
                node.right&&queue.push(node.right);
            }
        }
        minCount++;
    }
    return minCount;
};

递归法

/**
    * @param {TreeNode} root
    * @return {number}
    */
var minDepth1 = function(root) {
    if(!root) return 0;
    // 到叶子节点 返回 1
    if(!root.left && !root.right) return 1;
    // 只有右节点时 递归右节点
    if(!root.left) return 1 + minDepth(root.right);、
    // 只有左节点时 递归左节点
    if(!root.right) return 1 + minDepth(root.left);
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};