Construct Binary Tree from Preorder and Inorder Traversal

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

Не в общем случае. Прямой обход [1, 2] и обратный обход [2, 1] подходят и для левого, и для правого потомка, потому что ни один из этих обходов не помещает корень между его поддеревьями. Этой пары достаточно только для полного двоичного дерева, где у каждого узла ноль или два потомка.

СреднеОбход деревьев Хеширование Рекурсия

+10

Даны два массива — preorder и inorder, в которых перечислены различные значения узлов одного и того же бинарного дерева. При прямом обходе сначала посещают узел, затем его левое поддерево, а затем правое. При симметричном обходе сначала посещают левое поддерево, затем узел, а затем правое.

Восстановите дерево и верните его в виде массива в порядке обхода по уровням: корень находится по индексу 0, потомки элемента с индексом i — по индексам 2i+1 (левый) и 2i+2 (правый), а для каждой пустой позиции укажите -1. Массив заканчивается на последнем узле, без завершающих значений -1.

Функция

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: значения в порядке прямого обхода: узел, левое поддерево, правое поддерево
inorderinteger-array: значения в порядке inorder: левое поддерево, узел, правое поддерево
Возвращаетinteger-array: дерево в порядке обхода по уровням, где -1 обозначает пустые позиции, без завершающего -1

Ограничения

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, и все значения различны.
inorder содержит те же значения, и оба массива описывают одно и то же бинарное дерево.
Глубина дерева не превышает 14, поэтому каждый индекс в ответе меньше 2¹⁴-1 = 16383.

Примеры

Ввод: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Вывод: [7, 3, 4, 0, 9, -1, 6]
Пояснение: Прямой обход начинается с корня, 7. Он находится на позиции 3 в inorder, поэтому 0, 3, 9 идут влево, а 4, 6 — вправо. У 4 есть только правый потомок — 6, поэтому индекс 5 остаётся равным -1.

Ввод: preorder = [1, 2, 3]inorder = [2, 3, 1]
Вывод: [1, 2, -1, -1, 3]
Пояснение: Корень 1 стоит последним в inorder, поэтому индекс 2 равен -1. Среди 2, 3 в preorder сначала указано 2, а в inorder после него стоит 3, поэтому 3 — его правый потомок с индексом 4.

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

Сможешь ли ты восстановить дерево без рекурсии, за один проход по preorder с явным стеком?

Подсказки

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

Открыто 0 из 3

Решение

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

Рекурсивное разбиение с поиском корня

Идея

При обходе в прямом порядке левое поддерево следует за корнем и занимает по одной позиции на каждое значение — m-lo позиций, где m — позиция корня при симметричном обходе. Правое поддерево идёт после него, поэтому его корень находится по индексу pre+1+(m-lo). В первом примере в левой части 0, 3, 9 три значения, поэтому правое поддерево начинается с индекса 4 в обходе в прямом порядке — со значения 4.

Глубина не более 14 гарантирует, что каждый выходной индекс будет меньше 2^14-1. Заполните столько ячеек значением -1, запишите каждое значение по его индексу и в конце удалите завершающие записи -1.

Поиск корня в каждом диапазоне при симметричном обходе требует O(n·h): диапазоны на одном уровне не пересекаются, поэтому за один уровень просматривается не более n записей, то есть здесь — не более 14 × 3000 = 42000 шагов. Без ограничения глубины дерево в форме цепочки приводит к сложности O(n²).

Алгоритм

Создай out с 2^14-1 элементами, каждый из которых равен -1.
Напиши build(pre, lo, hi, h): если lo > hi, вернись. Иначе запиши preorder[pre] в out[h].
Просканируй inorder от lo, чтобы найти позицию корня m. Левое поддерево содержит m-lo значений.
Вызови build(pre+1, lo, m-1, 2*h+1) и build(pre+1+(m-lo), m+1, hi, 2*h+2).
Вызови build(0, 0, n-1, 0), затем удали завершающие элементы -1 и верни оставшиеся.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Рекурсивно разделить с помощью карты позиций

Идея

Значения различны, поэтому каждое из них встречается в inorder ровно на одной позиции. До начала рекурсии запишите соответствие между значением и позицией в отображение, и поиск каждого корня будет занимать один шаг.

Построение отображения занимает O(n), а затем каждое значение размещается ровно один раз за постоянное время, поэтому общая временная сложность составляет O(n). Отображение занимает O(n) памяти, а рекурсия — по одному кадру на каждый уровень. В C и R значения не превышают 10^4, поэтому в качестве отображения подойдёт обычный массив из 10^4+1 элементов.

Алгоритм

Создайте отображение, связывающее каждое значение inorder с его позицией.
Создайте out с 2^14-1 элементами, все равны -1.
В build(pre, lo, hi, h) выполните возврат, если lo > hi; иначе запишите preorder[pre] в out[h] и найдите его позицию m в отображении.
Выполните рекурсивные вызовы build(pre+1, lo, m-1, 2*h+1) и build(pre+1+(m-lo), m+1, hi, 2*h+2).
Вызовите build(0, 0, n-1, 0), затем удалите завершающие элементы -1 и верните оставшиеся.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

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

Начинать правое поддерево с pre+1+m, а не с pre+1+(m-lo). Это работает, пока lo равно 0, как при верхнем вызове, и перестаёт работать, когда диапазон начинается позже.
Пропускать промежутки. Отсутствующий потомок всё равно занимает своё место, поэтому второй пример возвращает [1, 2, -1, -1, 3], а не [1, 2, 3].
Оставлять завершающие элементы -1. Возврат всех 2^14-1 ячеек добавляет к первому примеру 16376 лишних элементов -1.
Копировать срезы обоих массивов при каждом вызове — это добавляет O(n) на каждом уровне. Передавайте диапазоны индексов.
В Lua и R массивы начинаются с 1. Для вычислений используйте позиции с отсчётом от 0, а считывайте preorder[pre + 1] и out[h + 1].

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

Зачем нужны и прямой, и симметричный обходы, чтобы восстановить бинарное дерево?

Одного прямого обхода недостаточно, чтобы определить структуру дерева. Прямому обходу [1, 2] соответствует дерево, в котором 2 — левый потомок 1, а также дерево, в котором он — правый потомок. Симметричный обход определяет структуру: [2, 1] помещает 2 слева, а [1, 2] — справа. Если значения различны, эта пара однозначно описывает одно дерево.

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

С отображением значений в их позициях при симметричном обходе время составляет O(n), а дополнительная память — O(n). Без отображения поиск корня в каждом диапазоне симметричного обхода занимает O(n·h), что для дерева в форме цепочки становится O(n²).

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

Не в общем случае. Прямой обход [1, 2] и обратный обход [2, 1] подходят и для левого, и для правого потомка, потому что ни один из этих обходов не помещает корень между его поддеревьями. Этой пары достаточно только для полного двоичного дерева, где у каждого узла ноль или два потомка.

def buildTree(preorder, inorder):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

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

[7, 3, 4, 0, 9, -1, 6]