Binary Tree Level Order Traversal

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

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

Q: Как понять, где заканчивается один уровень при поиске в ширину?

Считывайте размер очереди в начале каждого раунда и извлекайте ровно столько узлов. Подойдут и два других способа: хранить текущий и следующий уровни в отдельных списках или добавлять в очередь маркер после каждого уровня.

Q: Массив уже хранится по уровням. Почему бы не читать его фрагментами?

Для этого формата это работает так: уровень d , где корень находится на позиции 0, заполняет индексы с 2^d-1 по 2^(d+1)-2 , поэтому собирай непустые значения каждого диапазона, пока не встретится диапазон без значений. На собеседованиях обычно передают вместо этого объекты узлов с указателями, и из этой формы сохраняется только очередь.

СреднеОбход деревьев Очередь

+10

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

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

Функция

levelOrder(tree: integer-array) → integer-2d-array

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

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] — это -1 или значение, для которого 0 ≤ tree[i] ≤ 1000.
tree[0] никогда не равно -1, поэтому в дереве есть как минимум один узел.
В массиве после последнего узла могут быть дополнительные элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.

Примеры

Ввод: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Вывод: [[4], [9, 2], [6, 8, 5], [3]]
Пояснение: Индекс 3 пуст, поэтому у 9 есть только правый потомок — 6. На третьем уровне находятся 6, 8, 5, а 3 с индексом 9, расположенная под 6, находится одна на четвёртом уровне.

Ввод: tree = [7, -1, -1]
Вывод: [[7]]
Пояснение: Оба потомка корневого узла — -1, поэтому дерево состоит из одного узла 7 и имеет один уровень.

Ввод: tree = [1, 3, -1, 5, -1, -1, -1]
Вывод: [[1], [3], [5]]
Пояснение: У каждого узла есть только левый потомок: 3 с индексом 1 и 5 с индексом 3. На каждом уровне хранится одно значение, а завершающие элементы -1 ничего не добавляют.

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

Можешь вернуть уровни в зигзагообразном порядке: первый — слева направо, второй — справа налево и так далее, не сортируя ни один уровень?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Поиск в глубину, упорядоченный по глубине

Идея

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

Каждый список получается упорядоченным слева направо, потому что обход завершает обработку левого поддерева вершины, прежде чем перейти к правому. Из двух вершин на одном уровне первой достигается та, чей путь поворачивает налево в месте разделения путей. В примере 1 порядок посещения 4, 9, 6, 3, 2, 8, 5 заполняет списки [4], [9, 2], [6, 8, 5], [3].

Каждая вершина посещается один раз: время O(n), глубина рекурсии равна глубине дерева и составляет не более 14 уровней.

Алгоритм

Создайте пустой список уровней.
Посетите корень с глубиной 0.
В узле i с глубиной d остановитесь, если i выходит за пределы или tree[i] равно -1.
Если списков всего d, добавьте пустой список. Добавьте tree[i] в список d.
Посетите 2i+1, затем 2i+2, оба с глубиной d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Поиск в ширину: один уровень за раунд

Идея

Извлекайте узел из очереди и добавляйте в неё его дочерние узлы, сначала левый. Уровень d+1 добавляется только тогда, когда узлы уровня d покидают очередь, поэтому узлы выходят по уровням, слева направо.

Чтобы разделить этот поток на уровни, считывайте размер очереди в начале каждого раунда. Предыдущего уровня уже нет, а следующий ещё не появился, поэтому в очереди находятся ровно узлы текущего уровня. Извлеките столько узлов в одну строку; их дочерние узлы подождут следующего раунда. В примере 1 за раунды извлекаются 1, 2, 3 и 1 узел.

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

Алгоритм

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

from collections import deque


def levelOrder(tree):
    n = len(tree)
    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(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

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

Чтение размера очереди, пока вы её опустошаете. В while (j < queue.length) длина растёт по мере появления потомков, поэтому следующий уровень попадает в текущую строку.
Добавление правого потомка перед левым или посещение правого поддерева первым. Тогда второй уровень в примере 1 будет таким: [2, 9].
Пропуск проверки границы child < n. Потомки самых глубоких узлов находятся за концом массива.
Удаление элементов из начала обычного списка на основе массива, из-за чего во многих языках вся очередь каждый раз сдвигается. Используйте настоящую очередь или индекс начала.
Считать -1 узлом. Он никогда не попадает ни в строку, ни в очередь: [7, -1, -1] даёт [[7]], а не [[7], []].

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

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

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

Как понять, где заканчивается один уровень при поиске в ширину?

Считывайте размер очереди в начале каждого раунда и извлекайте ровно столько узлов. Подойдут и два других способа: хранить текущий и следующий уровни в отдельных списках или добавлять в очередь маркер после каждого уровня.

Массив уже хранится по уровням. Почему бы не читать его фрагментами?

Для этого формата это работает так: уровень d, где корень находится на позиции 0, заполняет индексы с 2^d-1 по 2^(d+1)-2, поэтому собирай непустые значения каждого диапазона, пока не встретится диапазон без значений. На собеседованиях обычно передают вместо этого объекты узлов с указателями, и из этой формы сохраняется только очередь.

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

Тест #1

Тест #2

Тест #3

Аргумент

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

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

[[4], [9, 2], [6, 8, 5], [3]]