Binary Tree Level Order Traversal

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

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

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

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

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

Да. Передайте каждому узлу его глубину и добавьте его значение в список для этой глубины. Пока обход посещает левое поддерево раньше правого, каждый список будет упорядочен слева направо. Это также O(n) ; поиск в ширину подходит лучше, поскольку он формирует уровни по порядку.

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

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

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

+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]]
Пояснение: У корня 4 есть потомки 9 и 2 с индексами 1 и 2. Индекс 3 пуст, поэтому на третьем уровне находится 6 (индекс 4, под 9), затем 8 и 5 (индексы 5 и 6, под 2). 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 ничего не добавляют.

+15 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

В глубину, упорядоченный по глубине

Идея

Сначала разберёмся, как перемещаться по массиву. Левый потомок узла с индексом i находится по индексу 2i+1, а правый — по индексу 2i+2. Потомок отсутствует, если его индекс выходит за пределы массива или по этому индексу хранится -1. В примере 1 потомки узла 9 (индекс 1) находятся по индексам 3 и 4, где хранятся значения -1 и 6, поэтому у узла 9 есть только правый потомок.

Теперь обойдём дерево в глубину и будем передавать каждому узлу его глубину: для корня она равна 0. Для каждой глубины заведём отдельный список. Когда достигнем узла глубины d, добавим его значение в список d; если к этому моменту есть только d списков, значит, это первый узел нового уровня, поэтому сначала создадим новый список.

Почему узлы каждого уровня оказываются в порядке слева направо? Обход полностью проходит левое поддерево узла, прежде чем перейти к правому. Возьмём два узла на одном уровне: в месте, где расходятся их пути от корня, один путь идёт влево, а другой — вправо, и обход сначала достигает узла слева. В примере 1 порядок такой: 4, 9, 6, 3, 2, 8, 5, и списки заполняются так: [4], [9, 2], [6, 8, 5], [3].

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

Алгоритм

Создай пустой список уровней.
Посети корень с глубиной 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, поэтому все узлы уровня d извлекаются до того, как будет извлечён любой узел уровня d+1, а внутри одного уровня узлы извлекаются слева направо.

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

В примере 1 очередь начинается со значения [4]: извлекаем 1 узел, получаем строку [4], в очередь поступают 9, 2. Извлекаем 2 узла, получаем строку [9, 2], в очередь поступают 6, 8, 5. Извлекаем 3 узла, получаем строку [6, 8, 5], в очередь поступает 3. Извлекаем 1 узел, получаем строку [3], очередь пуста.

Каждый узел один раз попадает в очередь и один раз извлекается из неё, поэтому время работы составляет O(n). В очереди находится не больше примерно одного уровня — до 16384 узлов на самом глубоком уровне полного дерева глубины 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 как значения. Пустая ячейка — это не узел, поэтому она не попадает ни в строку, ни в очередь.
Забытый контроль границ. Потомки самых глубоких узлов могут находиться за концом массива, поэтому проверяйте child < n, прежде чем читать tree[child].
Возврат пустых уровней. В конечных элементах -1 нет узлов, поэтому ответ для [7, -1, -1] — [[7]], а не [[7], []].

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

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

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

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

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

Можно ли выполнить обход в порядке уровней с помощью поиска в глубину?

Да. Передайте каждому узлу его глубину и добавьте его значение в список для этой глубины. Пока обход посещает левое поддерево раньше правого, каждый список будет упорядочен слева направо. Это также O(n); поиск в ширину подходит лучше, поскольку он формирует уровни по порядку.

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

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