Invert Binary Tree

+10

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

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

Функция

invertTree(tree: integer-array) → integer-array

treeinteger-array: двоичное дерево в порядке уровней, где -1 обозначает пустое место
Возвращаетinteger-array: зеркальное дерево в порядке уровней, без завершающих элементов -1

Ограничения

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

Примеры

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

Ввод: tree = [2, 7, -1, 6]
Вывод: [2, -1, 7, -1, -1, -1, 6]
Пояснение: Цепочка 2, 7, 6 наклонена влево, а её зеркальное отражение — вправо. 7 перемещается с индекса 1 на индекс 2, а 6 — с индекса 3 на индекс 6, поэтому ответ длиннее входных данных: во всех пустых позициях перед последним узлом стоит -1.

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

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

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

Как бы вы проверили, является ли дерево зеркальным отражением самого себя, используя те же пары индексов, но не создавая перевёрнутую копию?

Подсказки

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

Открыто 0 из 3

Решение

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

Рекурсия, которая размещает каждый узел на зеркальном индексе

Идея

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

Теперь отзеркалим дерево. Корень остаётся с индексом 0. Левое поддерево узла становится правым поддеревом его зеркальной копии, а правое — левым. Поэтому, если узел с индексом src попадает в ответ на индекс dst, его левый потомок попадает на 2*dst+2, а правый — на 2*dst+1. Напиши place(src, dst): скопируй значение, затем вызови place(2*src+1, 2*dst+2) и place(2*src+2, 2*dst+1). Если место пустое, сразу вернись. В первом примере узел 3 с индексом 1 попадает на индекс 2, поэтому его левый потомок 1 попадает на индекс 6, а правый потомок 4 — на индекс 5.

Узел никогда не меняет уровень, поэтому его зеркальный индекс остаётся на том же уровне, что и исходный. Округли длину вверх до целого числа уровней (1, 3, 7, 15, ...), заполни такое количество ячеек значениями -1, а в конце удали конечные элементы -1. Во втором примере длина 4 округляется до 7, благодаря чему остаётся место для узла 6 с индексом 6.

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

Алгоритм

Округли длину вверх до size = 2^k - 1 и заполни выходной массив такого размера значениями -1.
Напиши place(src, dst): если src выходит за конец или tree[src] равно -1, вернись.
Иначе задай out[dst] = tree[src], затем вызови place(2*src+1, 2*dst+2) и place(2*src+2, 2*dst+1).
Вызови place(0, 0), удали конечные элементы -1 и верни выходной массив.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

Поиск в ширину с очередью пар индексов

Идея

Те же пары работают и без рекурсии. Поместите (0, 0) в очередь: корень и место, куда он переходит. Возьмите пару (src, dst) из начала очереди, скопируйте tree[src] в out[dst] и добавьте в очередь каждого существующего потомка с переставленным индексом назначения: левого потомка 2*src+1 с 2*dst+2, правого потомка 2*src+2 с 2*dst+1.

Это классический итеративный вариант инверсии. Если используются объекты узлов, вы берёте узел из очереди, меняете местами двух его потомков и добавляете их в очередь. Здесь перестановка записывается в индекс назначения, поскольку массив не может за один шаг поменять местами целые поддеревья. Каждый существующий узел попадает в очередь один раз, с указанием точного места, которому он соответствует, поэтому в выходном массиве каждый узел оказывается на зеркальном месте. В первом примере получаются пары (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

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

Алгоритм

Округлите длину вверх до целого числа уровней и заполните выходной массив такого размера значениями -1.
Поместите пару (0, 0) в очередь.
Возьмите пару (src, dst) из начала очереди и задайте out[dst] = tree[src].
Добавьте в очередь (2*src+1, 2*dst+2) и (2*src+2, 2*dst+1) для каждого дочернего узла, который находится внутри массива и не равен -1.
Когда очередь опустеет, удалите завершающие элементы -1 и верните выходной массив.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

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

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

Перестановка tree[2*i+1] и tree[2*i+2] на месте. Это меняет местами два значения, но не поддеревья под ними. Перестановка индексов 1 и 2 в первом примере оставляет 1 и 4 висящими под 8.
Создание выходного массива той же длины, что и входной. Зеркально отражённый узел может оказаться за последним индексом входного массива, как это происходит с 6 во втором примере. Задавайте размер выходного массива с учётом целых уровней.
Забыть обрезать массив. В конце ответа не должно быть -1 — ни для дополненных входных данных, ни для деревьев, зеркальное отражение которых заканчивается раньше, чем исходный массив.
Разворот всего массива. Так уровни перемешаются: последний лист станет корнем.
Пропуск проверки границ. Индекс дочернего узла может выходить за конец входного массива, поскольку массив может заканчиваться сразу после последнего узла.
Путаница со смещением в Lua и R, где массивы начинаются с 1. Используйте индексацию с 0 для вычисления 2*i+1 и считывайте tree[i + 1].

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

Что значит инвертировать бинарное дерево?

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

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

Каждый узел посещается один раз, поэтому временная сложность составляет O(n). Рекурсивное решение использует O(h) памяти стека для дерева глубины h, а решение на основе очереди — O(w) для самого широкого уровня. В этой версии с массивом сам результат представляет собой новый массив, что добавляет O(n).

Как инвертировать бинарное дерево без рекурсии?

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

Почему инвертирование бинарного дерева переворачивает каждый уровень?

Зеркальное отражение меняет местами левую и правую стороны повсюду, поэтому узлы на каждом уровне располагаются в обратном порядке. При хранении в порядке уровней это означает, что срез массива для каждого уровня разворачивается: срез [1, 4, -1, 9] из первого примера после этого выглядит как [9, -1, 4, 1]. Разворот каждого уровня после дополнения последнего уровня значением -1 — это третий вариант решения с временной сложностью O(n), который работает только для такого представления массива.

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

[5, 8, 3, 9, -1, 4, 1]