Binary Tree Zigzag Level Order Traversal

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

Нужно выписать значения двоичного дерева по уровням, на каждом уровне меняя направление: верхний уровень слева направо, следующий справа налево и так далее. Наш пример: дерево [7, 4, 9, none, 5, 1, 11] по уровням — ответ [[7], [9, 4], [5, 1, 11]].

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

Пример: прочитать [7, 4, 9, none, 5, 1, 11] по уровням, разворачиваясь на каждом уровне.

7495111уровеньслева направо—очередьначало слева—
не достигнутждёт в очередитекущий, только что записанготов

Дерево не пустое

01/56
сначала · назад · пуск · шаг
Скорость
1function zigzagLevelOrder(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 leftToRight = true
7 while queue is not empty:
8 level = []
9 size = queue.size
10 repeat size times:
11 node = queue.popFront()
12 if leftToRight:
13 level.addBack(node.val)
14 else:
15 level.addFront(node.val)
16 for each child of node, left first:
17 queue.pushBack(child)
18 result.add(level)
19 leftToRight = not leftToRight
20 return result
состояние
result
–
queue
–
leftToRight
–
level
–
size
–
node
–
историянажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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