Binary Tree Right Side View
В массиве root хранится двоичное дерево. Корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце могут следовать дополнительные элементы -1.
Посмотри на дерево с правой стороны. На каждом уровне виден ровно один узел — самый правый, а остальные скрыты. Перечисли значения этих узлов от уровня корня до самого глубокого уровня.
Функция
- rootinteger-array
- дерево в порядке кучи, с -1 для пустого места
- Возвращаетinteger-array
- самое правое значение каждого уровня, начиная с верхнего
Ограничения
1 ≤ root.length ≤ 32767- Каждый
root[i]— это-1или значение, для которого0 ≤ root[i] ≤ 104. - Значения узлов различны.
root[0]никогда не равен-1, поэтому в дереве есть хотя бы один узел.- Массив может заканчиваться дополнительными элементами
-1после последнего узла. - Оба потомка пустого места тоже пусты, а дерево имеет не более
14уровней.
Примеры
- Ввод
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- Вывод
- [5, 9, 1, 3]
- Пояснение
- Справа ты видишь
5,9и1(индекс 6). На четвёртом уровне находится только3— индекс 8 под7в левом поддереве. Справа ничего не достигает такой глубины, поэтому3видно.
- Ввод
- root = [6, 0, -1, 8, -1, -1, -1]
- Вывод
- [6, 0, 8]
- Пояснение
- Дерево представляет собой цепочку левых потомков:
6,0,8. На каждом уровне находится один узел, поэтому ты видишь все три, хотя ни один из них не является правым потомком.
- Ввод
- root = [42]
- Вывод
- [42]
- Пояснение
- Массив длины 1: у корня
42вообще нет дочерних мест, и представление — это одно значение.
Дополнительный вопрос
Как получить вид дерева справа, если у каждого узла может быть любое количество дочерних узлов, хранящихся в списке слева направо?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Двигаясь вниз по правым потомкам примера 1, получаем
5, 9, 1и останавливаемся. В ответе есть четвёртое значение. Откуда оно берётся?Сгруппируйте узлы по глубине, а не по сторонам. Запишите каждый уровень слева направо: где в этом списке находится узел, который увидит человек справа?
Храни список
view. Выполняй обход в глубину с учётом глубины, сначала правого потомка, затем левого, и добавляй узел, когда его глубина равна длинеview. Можно также использовать очередь, обрабатывая по одному уровню за раунд: добавляй последний узел каждого раунда.
Решение
Вы видите самый правый узел каждого уровня, и он не обязательно является правым потомком: последнее значение в примере 1 находится в левом поддереве. При поиске в ширину этот узел оказывается последним в каждом раунде; при обходе в глубину, который сначала идёт вправо, он встречается раньше любого другого узла на своём уровне.
Поиск в ширину, последний узел на каждом уровне
Идея
Обрабатывайте дерево по одному уровню за раунд. В начале раунда очередь содержит ровно один уровень слева направо, поэтому последний индекс, который вы извлекаете из очереди в этом раунде, соответствует самому правому узлу этого уровня, а его значение добавляется в ответ.
В примере 1 раунды — это [5], [2, 9], [7, 4, 1] и [3], а их последние элементы дают 5, 9, 1, 3. Важен уровень, а не сторона: 3 находится в левом поддереве, но на своём уровне он один.
Каждый индекс добавляется в очередь и извлекается из неё один раз, поэтому временная сложность составляет O(n). Очередь может вырасти до ширины самого широкого уровня — в худшем случае это O(n).
Алгоритм
- Добавьте в очередь индекс корневого узла
0. - Начните раунд, сохранив длину очереди
s. - Извлеките из очереди
sиндексов. Для каждого индексаiдобавьте в очередь2i+1, а затем2i+2, если они меньше длины массива и не равны-1. - Добавьте значение последнего индекса, извлечённого в этом раунде.
- Повторяйте, пока очередь не опустеет, затем верните ответ.
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewПоиск в глубину, сначала правый потомок
Идея
Обходи дерево в глубину, сначала проверяя правого потомка, а затем левого, и передавай глубину, начиная с 0 в корне. Когда обход впервые достигает глубины d, в ответе содержится ровно d значений. Добавь значение узла, а все последующие узлы на этом уровне игнорируй.
Этот первый узел — самый правый: когда два пути к одному уровню расходятся, обход сначала следует по правой ветви до конца, а затем возвращается к левой. В примере 1 обход посещает 5, 9, 1, 2, 4, 7, 3: он пропускает 2, 4 и 7, поскольку для их глубин значения уже есть, и добавляет 3.
Каждый узел посещается один раз, время работы — O(n), в стеке — по одному вызову на уровень, не более 14.
Алгоритм
- Начни с пустого ответа и корня на глубине 0.
- Пропусти индекс, который выходит за конец массива, или содержит
-1. - Если длина ответа равна глубине, добавь значение: обход достиг нового уровня и достиг его справа.
- Сначала рекурсивно перейди к правому потомку
2i+2, затем к левому потомку2i+1, каждый раз на уровень глубже. - Верни ответ.
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
Ловушки и крайние случаи
- Следовать только по правым потомкам от корня. В примере 1 тогда получается
[5, 9, 1], а узел3пропускается; в примере 2 получается[6]. - Читать последний слот каждого уровня:
root[2^(d+1)-2]. В примере 2 по индексу 6 находится-1; видимый узел8находится по индексу 3. - Пропустить проверку длины для позиции потомка. В примере 1
3— последняя запись, поэтому позиции его потомков 17 и 18 не существуют. - Сначала помещать в очередь правого потомка, сохраняя при этом последний узел каждого прохода. Так собирается левый вид:
[5, 2, 7, 3]. - Позволять более поздним узлам перезаписывать более ранние при обходе справа налево — это также даёт левый вид.
Частые вопросы3
Какова временная и пространственная сложность задачи «Вид бинарного дерева справа»?
Время выполнения составляет O(n) для n узлов, и ни одно решение не может пропустить узлы, поскольку самый правый узел уровня может находиться где угодно. Объём памяти составляет O(w) для очереди, где w — ширина самого широкого уровня, или O(h) для обхода справа налево в дереве из h уровней.
Может ли поиск в глубину с обходом сначала влево решить эту задачу?
Да, если перезаписывать значение, а не сохранять первое. При обходе сначала слева на каждом уровне узлы встречаются слева направо, поэтому сохраняй значение каждого узла на его глубине, позволяя более поздним узлам заменять предыдущие. В конце на каждой глубине останется самое правое значение. Это по-прежнему O(n), но запись выполняется один раз для каждого узла.
Мне использовать поиск в ширину или поиск в глубину?
Оба алгоритма линейны. Поиск в ширину следует определению: один уровень за раунд. Поиск в глубину хранит только текущий путь, что экономит память на широком дереве, а его рекурсивная форма на несколько строк короче.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def rightSideView(root):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Ожидаемый вывод
[5, 9, 1, 3]