637. Average of Levels in Binary Tree

Задача

Дан корень бинарного дерева. Верните массив средних значений узлов на каждом уровне.

Примеры

Пример 1

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

Пояснение

Среднее на уровне 0 = 3, на уровне 1 = 14.5, на уровне 2 = 11.

Пример 2

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

Решение

Решение

/**
 * Time Complexity: O(n) - посещаем каждый узел ровно один раз
 * Space Complexity: O(w) - где w это максимальная ширина дерева (очередь содержит узлы одного уровня)
 */
var averageOfLevels = function(root) {
    const result = [];
    let currentLevel = [root];
 
    while (currentLevel.length > 0) {
        const nextLevel = [];
        let sum = 0;
 
        for (const node of currentLevel) {
            sum += node.val;
            if (node.left) nextLevel.push(node.left);
            if (node.right) nextLevel.push(node.right);
        }
 
        result.push(sum / currentLevel.length);
        currentLevel = nextLevel;
    }
 
    return result;
};