Vertical Order Traversal of a Binary Tree

СложноОбход деревьев Сортировка Хеширование

+10

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

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

Функция

verticalTraversal(root: integer-array) → integer-2d-array

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

Ограничения

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

Примеры

Ввод: root = [5, 2, 9, 4, 7, 1, 6]
Вывод: [[4], [2], [5, 1, 7], [9], [6]]
Пояснение: В столбце 0 находится корень 5, а двумя уровнями ниже — 7 и 1. Эти два узла находятся в одном столбце и на одной глубине, поэтому 1 идёт перед 7, хотя 7 расположен левее.

Ввод: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Вывод: [[2, 5], [1, 4], [3]]
Пояснение: В столбце -1 находятся 2 на глубине 1 и 5 на глубине 3 (левый потомок 4). В столбце 0 находятся корень 1 и 4 с индексом 4. В столбце 1 находится только 3.

Ввод: root = [6, -1, -1]
Вывод: [[6]]
Пояснение: У 6 нет дочерних элементов, поэтому ответ содержит один столбец: [6].

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

Каждое значение не превышает 5000. Можешь воспользоваться этим, чтобы отказаться от сортировки сравнением и выполнить задачу за O(n + 5000)?

Решение

У каждого узла есть три ключа: column, depth и value. Ответ — это узлы, упорядоченные по этим ключам, отдельный список для каждого столбца. Если значения column и depth совпадают, порядок определяется значением value, а не порядком слева направо, в котором обход встречает узлы, поэтому нужно выполнить сортировку: сразу всех узлов или каждого уровня при поиске в ширину.

Запишите каждый узел, затем отсортируйте

Идея

Посетите каждый узел один раз в любом порядке и запишите тройку (столбец, глубина, значение). Переход к дочернему узлу увеличивает глубину на 1 и смещает столбец на 1 влево или вправо. Затем отсортируйте тройки по столбцу, глубине и значению. Теперь узлы каждого столбца расположены рядом в нужном порядке. Пройдитесь по отсортированному списку и начинайте новый вложенный список при каждой смене столбца.

В примере 1 тройки столбца 0 сортируются так: (0, 0, 5), (0, 2, 1), (0, 2, 7). Сортировка, O(n log n), доминирует над проходом за O(n), а для троек требуется O(n) памяти.

Алгоритм

Поместите (индекс 0, столбец 0, глубина 0) в стек.
Извлеките узел, запишите (столбец, глубина, значение) и поместите в стек каждого существующего потомка со столбцом col-1 или col+1 и глубиной depth+1.
Когда стек опустеет, отсортируйте тройки по столбцу, затем по глубине, затем по значению.
Пройдите по ним, начиная новый список при каждом изменении столбца.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Сортируйте внутри каждого уровня, уровень за уровнем

Идея

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

В примере 1 узлы уровня 2 поступают как 4, 7, 1, 6 в столбцах -2, 0, 0, 2 и после сортировки располагаются как 4, 1, 7, 6, поэтому столбец 0 становится равен [5, 1, 7]. Занятые столбцы образуют один непрерывный диапазон, поэтому достаточно отслеживать наименьший и наибольший.

Сортировка уровня из m узлов требует O(m log m). В худшем случае сложность всё равно составляет O(n log n), поскольку на последнем уровне полного дерева находится примерно половина узлов. Пространственная сложность — O(n).

Алгоритм

Начни с уровня, содержащего узел (индекс 0, столбец 0).
Отсортируй уровень по столбцу, затем по значению.
В этом порядке добавь каждое значение в список его столбца, а его реальные дочерние узлы со столбцами col-1 и col+1 собери в следующий уровень.
Повторяй, пока уровень не опустеет, отслеживая наименьший и наибольший столбцы.
Верни списки от наименьшего столбца к наибольшему.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

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

Сохранять равные значения в порядке слева направо. Поиск в ширину без сортировки на каждом уровне выдаёт [5, 7, 1] для столбца 0 примера 1, а не [5, 1, 7].
Добавлять значения во время обхода в глубину без сортировки. В [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5] обход сначала слева добавляет 5 (глубина 3) в столбец 1 раньше, чем 3 (глубина 1).
Сортировать по столбцу и значению, но не по глубине. Тогда столбец 0 примера 1 будет иметь вид [1, 5, 7].
Использовать строки в качестве ключей столбцов. При сортировке как текста "-1" окажется перед "-2", поэтому столбцы слева от 0 будут выведены в неправильном порядке.

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

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

Сортировка всех узлов по столбцу, глубине и значению занимает O(n log n) и доминирует над обходом за O(n). Сортировка по уровням имеет ту же худшую оценку, поскольку на последнем уровне полного дерева находится примерно половина узлов. Требуемый объём памяти — O(n).

Можно ли выполнить обход в вертикальном порядке без сортировки?

Только если узлы с одинаковым значением идут слева направо. Тогда поиск в ширину, который добавляет каждое значение в список своего столбца, даёт ответ за O(n). Если узлы с одинаковым значением упорядочены по значению, потребуется сортировка, но только в пределах одного уровня, поскольку одинаковое значение может быть только у узлов одного уровня.

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

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

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

Тест #1

Тест #2

Тест #3

Аргумент

root = [5, 2, 9, 4, 7, 1, 6]

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

[[4], [2], [5, 1, 7], [9], [6]]