102. Binary Tree Level Order Traversal

Задача

Дан корень бинарного дерева. Верните обход по уровням (слева направо, уровень за уровнем).

Примеры

Пример 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Пример 2

Input: root = [1]
Output: [[1]]

Пример 3

Input: root = []
Output: []

Решение

Решение

/**
 * Time: O(n) — n = количество узлов (каждый узел обрабатывается один раз).
 * Space: O(w) для очереди (w = максимальная ширина дерева), и O(n) если считать output `result`.
 */
var levelOrder = function(root) {
    if (!root) return [];
 
    const queue = [root];
    const result = [];
    let head = 0;
 
    while (head < queue.length) {
        const levelValues = [];
        const headLength = queue.length;
 
        for (; head < headLength; head++) {
            const node = queue[head];
 
            levelValues.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
 
        result.push(levelValues);
    }
 
    return result;
};