Average of Levels in Binary Tree

Лёгкая№637узлы дерева

Дан корень двоичного дерева. Для каждого уровня сверху вниз нужно найти среднее его значений и вернуть средние списком. Наш пример — дерево [5, 3, 8, 2, 6, none, 10] по уровням: сверху 5, под ним 3 и 8, ниже 2, 6 и 10 — ответ [5, 5.5, 6].

637 Average of Levels in Binary TreeРазбор · 1×

Пример: найти среднее каждого уровня дерева 5 / 3, 8 / 2, 6, 10.

5382610очередьначало слева—
не достигнутв очереди, этот уровеньв очереди, следующий уровеньтекущийучтён в сумме

Средних пока нет: result = []

01/51
сначала · назад · пуск · шаг
Скорость
1function averageOfLevels(root):
2 result = []
3 queue = [root]
4 while queue is not empty:
5 size = queue.size
6 sum = 0
7 repeat size times:
8 node = queue.popFront()
9 sum = sum + node.val
10 if node.left is not none:
11 queue.pushBack(node.left)
12 if node.right is not none:
13 queue.pushBack(node.right)
14 result.add(sum / size)
15 return result
состояние
result
[]
queue
–
size
–
sum
–
node
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Когда уровень начинается, в очереди ровно этот уровень: уровень выше весь вынут, а из уровня ниже ещё никого нет.
  2. size запоминаем до того, как уровень положит в очередь своих потомков, поэтому цикл берёт ровно этот уровень, а сумма делится на его собственное число узлов.
  3. Каждый узел добавляет своё значение в сумму своего уровня один раз, поэтому каждое среднее считается по нужным значениям.

Сложность

Время O(n): каждый узел один раз попадает в очередь и один раз из неё выходит. Память O(w): в очереди не больше примерно двух уровней, w — самый широкий.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.