树的层次遍历（广度优先搜索BFS）

解题思路：采用树的层次遍历的方式(在图中叫广度优先遍历)，使用队列取存储待遍历的节点。程序的结束就是队列为空。
1.整体上，出队列的节点指向队列中的0号元素，比如1遍历完成之后2，3进队列，2出队列，那么2的next指向队列中的0号元素即可。但是存在问题就是3会指向4，而且1没有指向了。
2.这里用到一个技巧，我们知道一颗满二叉树，层数n对应的节点为2 ^ (n -1),那么层数n对应的节点总数就是2 ^ n - 1。我们用一个变量tag记录当前正在遍历的层数，用num记录当前已经遍历的节点数。每次遍历完当前层之后都向队列中添加一个null,这样就解决了1中出现的问题。如果遇到为空的就跳过本次循环即可。

代码实现如下

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    // let head = root
    let Queue = [] // 使用层次遍历的方式
    // 只有在2^n的时候才会向队列中添加null
    let tag = 1  // 这个记录层数
    let num = 0 // 这个记录节点的数量
    Queue.push(root)
    num++
    //判断是否应该进入下一层
    if((Math.pow(2,tag) - 1)===num){
        Queue.push(null)
        //接下来进入下一层
        tag++
    }
    while(Queue.length){
        let temp = Queue.shift()
        // 如果当前节点是空的时候就表示当前这层遍历结束
        if(!temp) continue
        temp.next = Queue[0]
        // 左右节点进队列
        Queue.push(temp.left)
        Queue.push(temp.right)
        num+=2
        //判断是否应该进入下一层
        if((Math.pow(2,tag) - 1) === num){
            Queue.push(null)
            //接下来进入下一层
            tag++
        }
    }
    return root
};