102 二叉树的层序遍历

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

题解

首先层序遍历应该利用队列来实现广度遍历。 其次怎么把结果一组一组的保存起来。

没有分组前的层序遍历

如果先不管分组的情况下，这种就是简单的队列应用，代码如下：

var levelOrderQueue = function(root) {
    const queue = []
    const result = []

    if(!root) {
        return result
    }
    queue.push(root)

    while(queue.length) {
        //先shift
        const current = queue.shift()
        result.push(current.val)
        if (current.left) {
            queue.push(current.left)
        }
        if(current.right) {
            queue.push(current.right)
        }
    }

    return result
}

怎么确定分组

分组其实就是要确定每一层有多少个节点。而我们每次广度遍历的时候，都是知道下一层到底有多少节点的。我们只需要一层处理完后就剩下一层的节点数。所以也就是队列的长度。我们在这里需要一次取出一层所有的节点而不是像上面那样一个个去存取。

var levelOrderQueue = function(root) {
    const queue = []
    const result = []

    if(!root) {
        return result
    }
    queue.push(root)

    while(queue.length) {
        const size = queue.length
        const temp = []
        //一次存多个，取多个，一次把当前层的取出，并push所有的到下一层
        for(let i=0;i<size;i++) {
            //先shift
            const current = queue.shift()
            temp.push(current.val)
            if (current.left) {
                queue.push(current.left)
            }
            if(current.right) {
                queue.push(current.right)
            }
        }
       result.push(temp)
    }

    return result
}

递归实现

递归实现其实也是按照深度优先遍历来，但是存储结果的步骤是按照不同层存在不同的结果集合里。

var levelOrderRecursive = function(root) {
    var levelOrderInner = function(root, level, result) {
        if(!root) {
            return
        }
        if(!result[level]) {
            result[level] = []
        }
        result[level].push(root.val)

        levelOrderInner(root.left, level +1, result)
        levelOrderInner(root.right, level + 1, result)
    }
    const result= []
    levelOrderInner(root, 0, result)
    return result
}