二叉树的层序遍历

题目描述

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

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

示例 2： 输入：root = [1]
输出：[[1]]

示例 3： 输入：root = []
输出：[]

思路&js代码

1、广度优先搜索

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;
};