102. 二叉树的层序遍历

[swiftwind0405]

方法一：广度优先搜索

解题思想：
利用广度优先遍历节点，同时记录当前的层数。
利用一个数组，保存层数索引相对的节点值。

代码：

var levelOrder = function(root) {
    if (!root) return [];
    const res = [];
    const q = [[root, 0]];
    while (q.length) {
        const [n, level] = q.shift();
        if (res[level]) {
            res[level].push(n.val)
        } else {
            res[level] = [n.val];
        }
        if (n.left) q.push([n.left, level + 1]);
        if (n.right) q.push([n.right, level + 1]);
    }
    return res;
};

复杂度分析：

• 时间复杂度：O(n)，最坏情况需要遍历所有节点。
• 空间复杂度：O(n)，最坏情况需要保存所有节点。