Задача: 637. Average of Levels in Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.

Пример:

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

👨‍💻 Алгоритм:

1⃣Обход дерева
Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

2⃣Подсчет среднего значения
Для каждого уровня дерева подсчитайте сумму значений узлов и количество узлов, чтобы вычислить среднее значение.

3⃣Сохранение результата
Сохраните среднее значение каждого уровня в массив и верните его.

😎 Решение:

function averageOfLevels($root) {
    $result = [];
    $queue = new SplQueue();
    $queue->enqueue($root);
    
    while (!$queue->isEmpty()) {
        $levelSum = 0;
        $levelCount = $queue->count();
        for ($i = 0; $i < $levelCount; $i++) {
            $node = $queue->dequeue();
            $levelSum += $node->val;
            if ($node->left) $queue->enqueue($node->left);
            if ($node->right) $queue->enqueue($node->right);
        }
        $result[] = $levelSum / $levelCount;
    }
    
    return $result;
}

Ставь 👍 и забирай 📚 Базу знаний