Binary Tree Zigzag Level Order Traversal
Тебе дано бинарное дерево, хранящееся в массиве root. Корень находится по индексу 0, дети узла с индексом i — по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1.
Верни значения узлов по уровням в зигзагообразном порядке: уровень корня — слева направо, следующий — справа налево и так далее, чередуя направление до самого глубокого уровня. Это также называется спиральным обходом уровней.
Функция
- rootinteger-array
- дерево в порядке кучи, с -1 для пустого места
- Возвращаетinteger-2d-array
- по одному списку значений для каждого уровня, начиная с верхнего и чередуя направление: слева направо и справа налево
Ограничения
1 ≤ root.length ≤ 32767- Каждый
root[i]равен-1или значению, для которого0 ≤ root[i] ≤ 104. - Значения узлов различны.
root[0]никогда не равно-1, поэтому дерево содержит как минимум один узел.- После последнего узла в массиве могут быть дополнительные элементы
-1. - Оба потомка пустого места тоже пусты, а дерево имеет не более
14уровней.
Примеры
- Ввод
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Вывод
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Пояснение
- Если читать слева направо, уровни такие:
8;12, 5;1, 9, 14;4, 2, 11. Уровни 1 и 3 идут в обратном порядке:[5, 12]и[11, 2, 4].
- Ввод
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Вывод
- [[1], [3, 2], [4, 5, 6, 7]]
- Пояснение
- Полное дерево из трёх уровней: средний уровень переворачивается в
[3, 2], а третий снова идёт слева направо. Две последние записи-1обозначают пустые места потомков узла4.
- Ввод
- root = [5]
- Вывод
- [[5]]
- Пояснение
- Один узел — это один уровень одного значения, читаемый в любом направлении.
Дополнительный вопрос
Можешь сразу поместить каждое значение на своё место в строке, не переворачивая и не используя второй стек?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Сначала собери уровни, каждый слева направо, как при обычном обходе в порядке уровней. Какие из этих списков нужно изменить и как?
Нумеруйте уровни, начиная с 0 в корне. Нечётные уровни читаются в обратном порядке. Разворот списка стоит столько же, сколько его чтение, поэтому разворот этих уровней сохраняет линейную сложность всей операции.
Чтобы пропустить обращение порядка, храните текущий уровень в стеке и добавляйте дочерние узлы во второй стек по мере извлечения: сначала левого дочернего узла, когда вы читаете слева направо, и сначала правого, когда читаете справа налево. Затем из второго стека извлекается следующий уровень в нужном вам порядке.
Решение
Уровни получаются в результате обычного поиска в ширину. Новая часть — направление: каждый второй уровень получается в обратном порядке. Либо разверни нечётные строки после их построения, либо помещай каждый уровень в стек, который возвращает элементы в порядке, обратном порядку их добавления.
Сначала обход по уровням, затем разворот каждого второго уровня
Идея
Очередь, обрабатывающая один уровень за раунд, возвращает каждый уровень слева направо. Пронумеруем уровни, начиная с 0 у корня: при зигзагообразном обходе нечётные уровни читаются справа налево, поэтому для получения ответа нужно развернуть именно эти строки.
Поиск посещает каждый узел один раз, а при развороте каждое значение затрагивается ещё раз, поэтому время работы составляет O(n).
Алгоритм
- Начните очередь с индексом
0. - В каждом раунде сохраните длину очереди
s, извлеките из очередиsиндексов в новую строку и добавьте в очередь существующих потомков каждого индекса: сначала левого, затем правого. - Если в ответе уже нечётное количество строк, разверните строку.
- Добавьте строку и продолжайте, пока очередь не опустеет.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsДва стека
Идея
Храни текущий уровень в стеке, из которого элементы извлекаются в направлении чтения уровня, и помещай детей каждого извлечённого узла во второй стек. Когда текущий стек опустеет, во втором будет следующий уровень.
Порядок добавления обеспечивает работу алгоритма. При извлечении слева направо добавляй сначала левого ребёнка каждого узла, затем правого: правый ребёнок самого правого узла окажется в стеке последним, поэтому элементы следующего уровня будут извлекаться с его правого конца. При извлечении справа налево добавляй сначала правого ребёнка, затем левого, и левый ребёнок самого левого узла окажется в стеке последним.
Пример 1: извлеки 8, добавь 12, 5. Извлеки 5, 12, затем добавь 14 от 5 и 9, 1 от 12. Извлеки 1, 9, 14, затем добавь 4, 2 от 9 и 11 от 14. Извлеки 11, 2, 4.
Каждый узел добавляется и извлекается один раз: время O(n), без прохода для разворота.
Алгоритм
- Помести индекс корня
0в стек и начни читать слева направо. - Пока стек не пуст, извлекай из него каждый индекс в новую строку, а существующих детей каждого извлечённого узла помещай во второй стек: сначала левого, затем правого при чтении слева направо, иначе — сначала правого, затем левого.
- Добавь строку в ответ.
- Сделай второй стек текущим, измени направление на противоположное и повтори.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Ловушки и крайние случаи
- Изменение порядка, в котором дочерние узлы попадают в одну очередь. Братья и сёстры меняются местами, но порядок родителей сохраняется: третий уровень примера 1 получается таким:
[9, 1, 14]. - Подсчёт уровней, начиная с 1. Каждый разворот смещает результат на один уровень, и в примере 1 получается
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]. - Использование одного порядка добавления на каждом уровне в версии с двумя стеками. В примере 1 третий уровень тогда извлекается как
[9, 1, 14]. - Добавление дочерних узлов в стек, из которого вы всё ещё извлекаете элементы. Они извлекаются до остальных узлов уровня своего родителя.
- Сортировка строки вместо её разворота. Последний уровень примера 1 должен быть
[11, 2, 4], а при сортировке такой результат не получается.
Частые вопросы3
В чём разница между зигзагообразным обходом и обходом по уровням?
Они обходят одни и те же уровни с теми же узлами. При обходе по уровням каждый уровень читается слева направо; при зигзагообразном обходе каждый второй уровень читается справа налево, начиная с уровня под корнем. Оба обхода выполняются за время O(n).
Обход зигзагом — это то же самое, что и обход дерева по спирали?
Да, оба названия описывают один и тот же обход. В некоторых текстах второй уровень начинают слева, а не справа, и это лишь сдвигает переключения на один уровень. Здесь уровень корня проходится слева направо, а следующий — справа налево.
Можно ли выполнить обход по уровням зигзагом с помощью дека?
Да. Храните каждый уровень в деке в порядке слева направо. На уровне слева направо извлекайте узлы из начала и добавляйте их потомков — сначала левого, затем правого — в конец. На уровне справа налево извлекайте узлы с конца и добавляйте их потомков — сначала правого, затем левого — в начало. Количество узлов, которое вы берёте в начале итерации, по-прежнему определяет уровень.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def zigzagLevelOrder(root):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Ожидаемый вывод
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]