Subtree of Another Tree

+10

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

Верните true, если у какого-либо узла root всё его поддерево имеет в точности такую же структуру и значения, как subRoot, и false в противном случае. Всё дерево root тоже считается.

Функция

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: дерево для поиска, в порядке уровней, где -1 обозначает пустое место
subRootinteger-array: дерево, которое нужно искать, в том же формате
Возвращаетboolean: истинно, если subRoot присутствует в root в качестве узла со всеми его потомками, иначе ложно

Ограничения

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

Примеры

Ввод: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Вывод: true
Пояснение: У узла 2 с индексом 1 есть дочерние узлы 1 и 3, и оба являются листьями. Это в точности subRoot.

Ввод: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Вывод: false
Пояснение: Узел 3 под узлом 2 теперь имеет потомка 0. Поддерево включает всех потомков, поэтому поддерево с корнем в узле 2 содержит четыре узла, тогда как у subRoot их три, и ни в одном другом узле нет 2.

Ввод: root = [5, 5, 7]subRoot = [5]
Вывод: true
Пояснение: У корня 5 два дочерних узла, поэтому он не совпадает с единственным узлом 5. Узел 5 с индексом 1 — листовой и совпадает.

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

Можешь ли ты определить отпечаток каждого поддерева по его значению и отпечаткам его дочерних узлов, чтобы сравнение с subRoot стоило O(1)? Что делать, если отпечатки двух разных поддеревьев совпали?

Подсказки

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

Открыто 0 из 3

Решение

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

Сравнивайте в каждом узле

Идея

Позиция i является реальной, если i находится внутри массива и значение там не равно -1. Два дерева идентичны, если оба пусты или если в их корнях хранится одно и то же значение, а их левые и правые поддеревья идентичны. same(i, j) одновременно обходит root, начиная с i, и subRoot, начиная с j. Если subRoot встречается в root, его корень находится в каком-то узле, поэтому попробуй выполнить same(i, 0) для каждого реального i.

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

Алгоритм

Напишите same(i, j). Если позиции i в root и j в subRoot обе пусты, верните true; если пуста ровно одна из них, верните false.
Если два значения различаются, верните false. В противном случае верните same(2*i+1, 2*j+1) и same(2*i+2, 2*j+2).
Верните true, если для некоторого действительного индекса i в root выполняется same(i, 0), и false в противном случае.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Сравнивайте только там, где высоты совпадают

Идея

У одинаковых деревьев одинаковая высота, которая считается как число узлов на самом длинном пути вниз. Поэтому стоит проверять только узлы root, высота которых равна высоте subRoot. В первом примере высота subRoot равна 2, а в root такую высоту имеют только 2 и 8.

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

Индексы потомков больше индекса их родителя, поэтому при сканировании от последнего индекса к первому оба потомка будут достигнуты раньше родителя. Два прохода для вычисления высоты и проверки занимают O(n + m) времени.

Алгоритм

Заполни массив высот для каждого дерева, просматривая его от последнего индекса до 0: пустая позиция получает 0, реальный узел получает 1 плюс большее из значений высоты двух его дочерних узлов.
Для каждого индекса i в root, высота которого равна высоте по индексу 0 в subRoot, выполни same(i, 0) и верни true, если условие выполняется.
Верни false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

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

Принятие частичного совпадения, как во втором примере. same должен завершиться неудачей, если в root есть узел на месте, где в subRoot пусто.
Остановка на первом узле с нужным значением. В третьем примере корень 5 не совпадает, а лист 5 под ним совпадает.
Сравнение срезов двух массивов. Узлы поддерева распределены по многим уровням, и в конце любого массива могут быть дополнительные элементы -1. Индекс за пределами массива соответствует пустому месту, как и -1.
В Lua и R сохраняйте индексы узлов начинающимися с 0 для арифметики 2*i+1 и читайте root[i + 1].

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

Какова временная сложность задачи «Поддерево другого дерева»?

Сравнение, начинающееся с каждого узла, в худшем случае требует O(n·m), где n и m — размеры двух деревьев. Если сравнивать только узлы, высота которых равна высоте subRoot, сложность составит O(n + m), поскольку каждый узел root обходится не более одного раза.

Можно ли решить задачу о том, является ли одно поддерево поддеревом другого дерева, с помощью сопоставления строк?

Да. Запишите каждое дерево в прямом порядке обхода, используя # для каждого пустого потомка и разделитель перед каждым значением: ,2,1,#,#,3,#,#. subRoot является поддеревом ровно тогда, когда его строка встречается внутри строки root, а KMP находит её за O(n + m). Без маркеров разные формы дают одинаковую строку; без разделителей 12 содержит 2.

Считается ли узел, который совпадает с subRoot, но имеет дополнительные дочерние узлы?

Нет. Поддерево — это узел вместе со всеми его потомками, поэтому каждый узел под найденным совпадением также должен присутствовать в subRoot. Во втором примере дополнительный 0 под 3 делает ответ false.

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

Тест #1

Тест #2

Тест #3

Аргументы

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

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

true