Left View of Binary Tree

+10

Дано бинарное дерево в виде массива root в порядке кучи: корень находится по индексу 0, дочерние узлы элемента с индексом i находятся по индексам 2*i+1 (слева) и 2*i+2 (справа), а -1 обозначает пустое место. В конце массива могут быть дополнительные элементы -1.

Встаньте слева от дерева. На каждом уровне вы видите один узел — самый левый; остальные узлы уровня скрыты за ним. Верните значения видимых узлов, начиная с верхнего уровня и далее вниз.

Функция

leftView(root: integer-array) → integer-array

rootinteger-array: дерево в порядке кучи, где для пустого места используется -1
Возвращаетinteger-array: самое левое значение каждого уровня, начиная с верхнего

Ограничения

1 ≤ root.length ≤ 32767
Каждый root[i] равен -1 или значению, для которого 0 ≤ root[i] ≤ 10⁴.
Значения узлов различны.
root[0] никогда не равен -1, поэтому в дереве есть как минимум один узел.
Массив может заканчиваться дополнительными элементами -1 после последнего узла.
Оба потомка пустого узла тоже пусты, и дерево имеет не более 14 уровней.

Примеры

Ввод: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Вывод: [3, 8, 6, 1]
Пояснение: 8 — лист, поэтому на третьем и четвёртом уровнях находятся только 6 (индекс 6) и 1 (индекс 13), оба под правым потомком 5. Вы всё равно их видите: [3, 8, 6, 1].

Ввод: root = [10, -1, -1]
Вывод: [10]
Пояснение: Индексы 1 и 2 содержат -1, поэтому у 10 нет потомков, и представление состоит только из корня.

Ввод: root = [1, 2, 3, 4, 5, 6, 7]
Вывод: [1, 2, 4]
Пояснение: Полное дерево из трёх уровней. Самые левые позиции уровней имеют индексы 0, 1 и 3 и содержат 1, 2 и 4.

Дополнительный вопрос

Уровень d заполняет индексы от 2^d-1 до 2^(d+1)-2. Сможешь построить представление, просматривая эти диапазоны без очереди и рекурсии? Какова стоимость этого для массива с дополнением?

Решение

Следование по левым потомкам от корня не сработает, если левое поддерево короче: в первом примере нижние уровни видны через правое поддерево. Вам нужен первый узел каждого уровня. Поиск в ширину выдаёт узлы каждого уровня слева направо; при обходе в глубину, который сначала идёт влево, первым встречается самый левый узел каждого уровня.

Поиск в ширину, первый узел каждого уровня

Идея

Очередь, обрабатываемая раундами, выдаёт уровни по одному. В начале раунда в очереди находится ровно один уровень, слева направо, потому что каждый ребёнок, добавленный в течение раунда, оказывается позади него. Извлеките столько индексов, сколько в нём элементов, добавьте в очередь детей каждого элемента, сначала левого, и сохраните первое значение.

В первом примере раунды — это [3], [8, 5], [6] и [1], и в них сохраняются значения 3, 8, 6 и 1. Элемент 8 ничего не добавляет, потому что в его дочерних позициях 3 и 4 находятся значения -1.

Каждый узел один раз добавляется в очередь и один раз извлекается из неё: время O(n). В очереди помещается целый уровень — до 8192 индексов в полном дереве из 14 уровней.

Алгоритм

Создай очередь, содержащую индекс 0, и пустой ответ.
Пока очередь не пуста, пусть s будет её размером, и удали s индексов. Добавь значение первого из них.
Для каждого удалённого индекса i добавь в очередь 2i+1, затем 2i+2, пропуская индексы за пределами конца и элементы, равные -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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

В глубину, сначала левый потомок

Идея

Обходите дерево в глубину: сначала левое поддерево, затем правое, передавая глубину каждого узла. Первый узел, которого достигает обход на глубине d, — самый левый на уровне d. Возьмите самый левый узел x уровня и любой узел y правее него: в последнем общем узле их путей x идёт влево, а y — вправо, и обход завершает левую ветвь, прежде чем перейти направо.

Обход спускается на один уровень за раз, поэтому, когда он впервые достигает глубины d, ответ содержит ровно d значений. Записывайте узел, когда d равно длине ответа; множество посещённых глубин не требуется.

Каждый узел посещается один раз, время — O(n), а память хранит один вызов на уровень, здесь их не более 14. Версия на R использует собственный стек и помещает правого потомка в стек перед левым.

Алгоритм

Создай пустой ответ и вызови visit(0, 0).
В visit(i, d) сразу выполни возврат, если i выходит за границы массива или root[i] равен -1.
Если d равно длине ответа, значит, обход впервые достиг уровня d: добавь root[i].
Вызови visit(2i+1, d+1), затем visit(2i+2, d+1).
Верни ответ после завершения первого вызова.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Ловушки и крайние случаи

Следование только по левым потомкам от корня. В первом примере обход останавливается на 8, пропуская 6 и 1.
Чтение первого элемента на каждом уровне, root[2^d-1]. В первом примере в первом элементе третьего уровня, с индексом 3, находится -1, а его единственный узел находится по индексу 6.
Посещение правого потомка первым при обходе в глубину. Тогда первым узлом, встреченным на каждом уровне, будет самый правый.
Чтение потомка без проверки границ. У 1 по индексу 13 есть места для потомков с индексами 27 и 28, которые выходят за пределы массива из 14 элементов.

Частые вопросы3

Левый вид — это то же самое, что левая граница дерева?

Нет. Левая граница — это путь: он начинается с левого потомка корня, идет налево, если может, иначе — направо, и останавливается перед листом. Левая проекция берет по одному узлу на каждом уровне из любой ветви. В первом примере граница пуста, поскольку 8 — лист, но проекция показывает 8, 6 и 1.

Какова временная и пространственная сложность левого вида?

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

Как изменить решение, чтобы получить правильный вид?

В версии с поиском в ширину сохраняйте последнее значение каждого раунда вместо первого. В версии с поиском в глубину сначала обходите правого потомка, а затем левого; тогда первый узел, которого достигает обход на каждом уровне, будет крайним справа.

def leftView(root):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Ожидаемый вывод

[3, 8, 6, 1]