Subtree of Another Tree

Q: Czy poddrzewo innego drzewa można znaleźć za pomocą dopasowywania ciągów znaków?

Tak. Zapisz każde drzewo w porządku preorder, używając # dla każdego pustego dziecka i separatora przed każdą wartością: ,2,1,#,#,3,#,# . subRoot jest poddrzewem dokładnie wtedy, gdy jego ciąg znaków pojawia się w ciągu znaków root , a KMP znajduje go w czasie O(n + m) . Bez znaczników różne kształty dają ten sam ciąg; bez separatorów 12 zawiera 2 .

ŁatwePrzechodzenie drzewa Rekurencja

+10

Otrzymujesz dwa drzewa binarne: root i subRoot, każde zapisane w tablicy w kolejności poziomami: korzeń znajduje się pod indeksem 0, dzieci elementu o indeksie i pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), a -1 oznacza puste miejsce. Tablica może kończyć się dodatkowymi wpisami -1.

Zwróć true, jeśli jakiś węzeł w root wraz ze wszystkimi jego potomkami ma dokładnie taki sam kształt i wartości jak subRoot, a w przeciwnym razie zwróć false. Liczy się również całe drzewo root.

Funkcja

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

rootinteger-array: drzewo do przeszukania, w kolejności poziomami, z wartością -1 w pustym miejscu
subRootinteger-array: drzewo, którego należy szukać, w tym samym formacie
Zwracaboolean: true, jeśli subRoot występuje w root jako węzeł ze wszystkimi swoimi potomkami, w przeciwnym razie false

Ograniczenia

1 ≤ root.length ≤ 32767 oraz 1 ≤ subRoot.length ≤ 32767
Każdy wpis to -1 lub wartość z zakresu od 0 do 10⁴.
root[0] i subRoot[0] nigdy nie są równe -1, więc oba drzewa mają co najmniej jeden węzeł.
Każda z tablic może kończyć się dodatkowymi wpisami -1 za swoim ostatnim węzłem.
Oboje dzieci pustego miejsca również są puste, a każde drzewo ma głębokość co najwyżej 14.
Wartości mogą się powtarzać.

Przykłady

Wejście: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Wyjście: true
Wyjaśnienie: Węzeł 2 o indeksie 1 ma dzieci 1 i 3, a oba są liśćmi. To właśnie subRoot.

Wejście: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Wyjście: false
Wyjaśnienie: 3 pod węzłem 2 ma teraz dziecko 0. Poddrzewo obejmuje wszystkich potomków, więc węzeł 2 zawiera cztery węzły, a subRoot trzy, i żaden inny węzeł nie ma wartości 2.

Wejście: root = [5, 5, 7]subRoot = [5]
Wyjście: true
Wyjaśnienie: Korzeń 5 ma dwoje dzieci, więc nie pasuje do pojedynczego węzła 5. 5 o indeksie 1 jest liściem i pasuje.

Pytanie dodatkowe

Czy potrafisz utworzyć odcisk palca każdego poddrzewa na podstawie jego wartości i odcisków palców jego dzieci, tak aby porównanie z subRoot miało koszt O(1)? Co zrobisz, gdy dwa różne poddrzewa dadzą kolizję?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Problem składa się z dwóch części: ustalenia, czy dwa drzewa są identyczne, oraz wyboru miejsca w root, w którym należy przeprowadzić to sprawdzenie. Pasować może tylko węzeł, którego wysokość jest równa wysokości subRoot, a węzły o tej samej wysokości nigdy się nie nakładają, więc sprawdzanie tylko ich sprawia, że każdy węzeł root jest odwiedzany najwyżej raz.

Porównuj w każdym węźle

Intuicja

Pozycja i jest rzeczywista, gdy i znajduje się w tablicy, a wartość w tym miejscu nie jest równa -1. Dwa drzewa są identyczne, gdy oba są puste albo gdy ich korzenie mają tę samą wartość, a ich lewe i prawe poddrzewa są identyczne. same(i, j) równolegle przechodzi przez root od i i przez subRoot od j. Jeśli subRoot występuje w root, jego korzeń znajduje się w jakimś węźle, więc sprawdź same(i, 0) dla każdego rzeczywistego i.

Prawie zgodność może trwać do m kroków, zanim się nie powiedzie, dla każdego z n węzłów: O(n·m). Tutaj ogranicza to limit głębokości: węzeł jest odwiedzany tylko przez sprawdzenia rozpoczynające się w nim lub powyżej niego, najwyżej 14 razy.

Algorytm

Napisz same(i, j). Jeśli pozycje i w root i j w subRoot są obie puste, zwróć true; jeśli pusta jest dokładnie jedna z nich, zwróć false.
Jeśli te dwie wartości są różne, zwróć false. W przeciwnym razie zwróć same(2*i+1, 2*j+1) i same(2*i+2, 2*j+2).
Zwróć true, jeśli same(i, 0) zachodzi dla jakiegoś rzeczywistego indeksu i w root, a w przeciwnym razie zwróć 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

Porównuj tylko tam, gdzie wysokości są takie same

Intuicja

Identyczne drzewa mają tę samą wysokość, liczoną jako liczbę węzłów na najdłuższej ścieżce w dół. Dlatego warto sprawdzić tylko te węzły root, których wysokość jest równa wysokości subRoot. W pierwszym przykładzie subRoot ma wysokość 2, a w root tę wysokość mają tylko 2 i 8.

Węzeł jest wyższy od każdego węzła poniżej niego, więc dwa węzły o tej samej wysokości nigdy nie znajdują się jeden wewnątrz drugiego. Każde sprawdzenie przechodzi tylko przez poddrzewo swojego węzła początkowego, więc łącznie sprawdzenia przechodzą przez każdy węzeł root najwyżej raz.

Dzieci znajdują się pod indeksami większymi niż indeks rodzica, więc skanowanie od ostatniego indeksu w dół dociera do obojga dzieci przed rodzicem. Dwa skanowania wysokości i sprawdzenia zajmują O(n + m) czasu.

Algorytm

Wypełnij tablicę wysokości dla każdego drzewa, skanując od ostatniego indeksu w dół do 0: puste miejsce otrzymuje 0, a rzeczywisty węzeł otrzymuje 1 plus większą wysokość jego dwojga dzieci.
Dla każdego indeksu i w root, którego wysokość jest równa wysokości pod indeksem 0 w subRoot, uruchom same(i, 0) i zwróć true, jeśli warunek jest spełniony.
Zwróć 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

Pułapki i przypadki brzegowe

Akceptowanie częściowego dopasowania, jak w drugim przykładzie. same musi zwrócić fałsz, gdy root ma węzeł w miejscu, w którym subRoot ma puste miejsce.
Zatrzymywanie się na pierwszym węźle o właściwej wartości. W trzecim przykładzie korzeń 5 nie pasuje, a pasuje znajdujący się pod nim liść 5.
Porównywanie fragmentów dwóch tablic. Węzły poddrzewa są rozmieszczone na wielu poziomach, a każda z tablic może kończyć się dodatkowymi wpisami -1. Indeks poza końcem tablicy oznacza puste miejsce, tak samo jak -1.
W Lua i R indeksy węzłów powinny pozostać 0-indeksowane dla obliczenia 2*i+1, a odczyt powinien odbywać się z root[i + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu „Poddrzewo innego drzewa”?

Porównywanie od każdego węzła kosztuje w najgorszym przypadku O(n·m), gdzie n i m to rozmiary obu drzew. Porównywanie tylko w węzłach, których wysokość jest równa wysokości subRoot, zmniejsza koszt do O(n + m), ponieważ każdy węzeł root jest wtedy odwiedzany najwyżej raz.

Czy poddrzewo innego drzewa można znaleźć za pomocą dopasowywania ciągów znaków?

Tak. Zapisz każde drzewo w porządku preorder, używając # dla każdego pustego dziecka i separatora przed każdą wartością: ,2,1,#,#,3,#,#. subRoot jest poddrzewem dokładnie wtedy, gdy jego ciąg znaków pojawia się w ciągu znaków root, a KMP znajduje go w czasie O(n + m). Bez znaczników różne kształty dają ten sam ciąg; bez separatorów 12 zawiera 2.

Czy węzeł pasujący do subRoot, ale mający dodatkowe dzieci, się liczy?

Nie. Poddrzewo to węzeł wraz ze wszystkimi jego potomkami, więc każdy węzeł znajdujący się pod dopasowanym węzłem musi również występować w subRoot. W drugim przykładzie dodatkowe 0 pod 3 sprawia, że odpowiedź to false.

def isSubtree(root, subRoot):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

true