(JS栈) LeetCode102. 二叉树的层序遍历

题目：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

方法一 递归
思路：
1、输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表。
2、将当前节点插入到对应层的列表 levels[level] 中。
3、递归非空的孩子节点：helper(node.left / node.right, level + 1)。

时间复杂度:O(n)
空间复杂度:O(n)

var levelOrder = function(root) {
    let levels = [];
    if(!root)
        return levels;
    
    let helper = (node, level)=>{
        if (levels.length == level)
            levels.push([]);

        levels[level].push(node.val);

        if (node.left)
            helper(node.left, level + 1);
        if (node.right)
            helper(node.right, level + 1);
    }
       
    helper(root, 0);
    return levels
}; 

方法二 迭代
时间复杂度:O(n)
空间复杂度:O(n)

var levelOrder = function(root) {
    levels = []
    if (!root)
        return levels;
    
    level = 0
    queue = [root];
    while (queue.length){
        levels.push([])
        level_length = queue.length;
        
        for(let i = 0; i < level_length; i++){
            node = queue.shift()
            levels[level].push(node.val)
            
            if (node.left)
                queue.push(node.left)
            if (node.right)
                queue.push(node.right)
        
        }
            
        level += 1
    }
    return levels
};