Binary Tree Level Order Traversal

Средняя№102узлы дерева

Дан корень двоичного дерева, возможно none. Нужно вернуть его значения по уровням: по списку на уровень, сверху вниз, а внутри уровня слева направо. Наш пример — дерево [7, 4, 9, 1, none, 6, 12, none, 3, 8] по уровням — ответ [[7], [4, 9], [1, 6, 12], [3, 8]].

102 Binary Tree Level Order TraversalРазбор · 1×

Пример: выписать по уровням значения несимметричного дерева из четырёх уровней.

749161238очередьначало слева—
не достигнутв очереди, этот уровеньв очереди, следующий уровеньтекущийвыписан

Корень — 7, не none

01/62
сначала · назад · пуск · шаг
Скорость
1function levelOrder(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 while queue is not empty:
7 size = queue.size
8 level = []
9 for i from 1 to size:
10 node = queue.popFront()
11 level.add(node.val)
12 for each child of node that is not none:
13 queue.pushBack(child)
14 result.add(level)
15 return result
состояние
result
–
queue
–
size
–
level
–
i
–
node
–
child
–
историянажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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