Subtree of Another Tree

Q: Wie hoch ist die Zeitkomplexität von Subtree of Another Tree?

Ein Vergleich ab jedem Knoten kostet im schlimmsten Fall O(n·m) , wobei n und m die Größen der beiden Bäume sind. Werden Vergleiche nur an Knoten durchgeführt, deren Höhe der Höhe von subRoot entspricht, sinkt der Aufwand auf O(n + m) , da jeder Knoten von root dann höchstens einmal durchlaufen wird.

Q: Kann „Teilbaum eines anderen Baums“ mit Zeichenfolgenabgleich gelöst werden?

Ja. Schreibe jeden Baum in Preorder-Notation, mit # für jedes leere Kind und einem Trennzeichen vor jedem Wert: ,2,1,#,#,3,#,# . subRoot ist genau dann ein Teilbaum, wenn seine Zeichenfolge in der Zeichenfolge von root vorkommt, und KMP findet sie in O(n + m) . Ohne die Markierungen ergeben verschiedene Formen dieselbe Zeichenfolge; ohne Trennzeichen enthält 12 die 2 .

LeichtBaumdurchlauf Rekursion

+10

Du erhältst zwei Binärbäume, root und subRoot, die jeweils in einem Array in Ebenenreihenfolge gespeichert sind: die Wurzel an Index 0, die Kinder von Index i an den Indizes 2*i+1 (links) und 2*i+2 (rechts) und -1 für eine leere Stelle. Ein Array kann mit zusätzlichen -1-Einträgen enden.

Gib true zurück, wenn ein Knoten von root zusammen mit all seinen Nachkommen genau dieselbe Struktur und dieselben Werte wie subRoot hat, andernfalls false. Auch der gesamte Baum root zählt.

Funktion

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

rootinteger-array: der zu durchsuchende Baum in Ebenenreihenfolge, wobei -1 eine leere Stelle kennzeichnet
subRootinteger-array: der Baum, nach dem gesucht werden soll, im selben Format
Gibt zurückboolean: true, wenn subRoot in root als Knoten mit all seinen Nachkommen vorkommt, andernfalls false

Einschränkungen

1 ≤ root.length ≤ 32767 und 1 ≤ subRoot.length ≤ 32767
Jeder Eintrag ist -1 oder ein Wert von 0 bis 10⁴.
root[0] und subRoot[0] sind niemals -1, daher haben beide Bäume mindestens einen Knoten.
Jedes der beiden Arrays kann nach seinem letzten Knoten mit zusätzlichen -1-Einträgen enden.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und jeder Baum hat eine Tiefe von höchstens 14.
Werte können sich wiederholen.

Beispiele

Eingabe: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Ausgabe: true
Erklärung: Der Knoten 2 am Index 1 hat die Kinder 1 und 3, und beide sind Blätter. Das ist genau subRoot.

Eingabe: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Ausgabe: false
Erklärung: Die 3 unter dem Knoten 2 hat jetzt ein Kind 0. Ein Teilbaum umfasst alle Nachfahren, daher enthält der Knoten 2 vier Knoten gegenüber den drei von subRoot, und kein anderer Knoten enthält eine 2.

Eingabe: root = [5, 5, 7]subRoot = [5]
Ausgabe: true
Erklärung: Die Wurzel 5 hat zwei Kinder und stimmt daher nicht mit dem einzelnen Knoten 5 überein. Die 5 am Index 1 ist ein Blatt und stimmt überein.

Weiterführende Frage

Kannst du jeden Teilbaum anhand seines Werts und der Fingerabdrücke seiner Kinder identifizieren, sodass ein Vergleich mit subRoot O(1) kostet? Was machst du, wenn zwei verschiedene Teilbäume kollidieren?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Das Problem besteht aus zwei Teilen: zu entscheiden, ob zwei Bäume identisch sind, und auszuwählen, wo in root diese Prüfung ausgeführt wird. Nur ein Knoten, dessen Höhe der Höhe von subRoot entspricht, kann übereinstimmen, und Knoten derselben Höhe überschneiden sich nie. Wenn man nur diese prüft, wird jeder Knoten von root höchstens einmal durchlaufen.

Vergleiche an jedem Knoten

Idee

Eine Position i ist gültig, wenn i innerhalb des Arrays liegt und der Wert dort nicht -1 ist. Zwei Bäume sind identisch, wenn beide leer sind oder wenn ihre Wurzeln denselben Wert haben und ihre linken und rechten Teilbäume identisch sind. same(i, j) durchläuft root ab i und subRoot ab j Schritt für Schritt. Wenn subRoot in root vorkommt, sitzt seine Wurzel auf irgendeinem Knoten. Probiere also same(i, 0) für jede gültige Position i.

Eine beinahe Übereinstimmung kann von jedem der n Knoten aus bis zu m Schritte durchlaufen, bevor sie scheitert: O(n·m). Hier begrenzt die Tiefenobergrenze dies: Ein Knoten wird nur von den Prüfungen durchlaufen, die an ihm oder oberhalb von ihm beginnen, höchstens 14 Mal.

Algorithmus

Schreibe same(i, j). Wenn die Stelle i in root und die Stelle j in subRoot beide leer sind, gib true zurück; wenn genau eine leer ist, gib false zurück.
Wenn sich die beiden Werte unterscheiden, gib false zurück. Andernfalls gib same(2*i+1, 2*j+1) und same(2*i+2, 2*j+2) zurück.
Gib true zurück, wenn same(i, 0) für irgendeinen gültigen Index i von root gilt, und andernfalls 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

Vergleiche nur, wenn die Höhen übereinstimmen

Idee

Identische Bäume haben dieselbe Höhe, gezählt als die Anzahl der Knoten auf dem längsten Pfad nach unten. Daher lohnt es sich nur, die Knoten von root zu überprüfen, deren Höhe der Höhe von subRoot entspricht. Im ersten Beispiel hat subRoot die Höhe 2, und in root haben nur die 2 und die 8 diese Höhe.

Ein Knoten ist höher als jeder Knoten unter ihm, daher liegt niemals einer von zwei Knoten gleicher Höhe innerhalb des anderen. Jede Überprüfung durchläuft nur den Teilbaum ihres Startknotens, sodass die Überprüfungen zusammen jeden Knoten von root höchstens einmal durchlaufen.

Die Kinder haben größere Indizes als ihr Elternknoten, daher erreicht ein Durchlauf vom letzten Index abwärts beide Kinder vor dem Elternknoten. Die beiden Höhendurchläufe und die Überprüfungen benötigen eine Laufzeit von O(n + m).

Algorithmus

Fülle für jeden Baum ein Höhenarray aus, indem du vom letzten Index abwärts bis 0 gehst: Ein leerer Platz erhält 0, ein echter Knoten erhält 1 plus die größere Höhe seiner beiden Kinder.
Führe für jeden Index i von root, dessen Höhe der Höhe am Index 0 von subRoot entspricht, same(i, 0) aus und gib true zurück, wenn es zutrifft.
Gib false zurück.

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

Stolperfallen und Grenzfälle

Eine teilweise Übereinstimmung zulassen, wie im zweiten Beispiel. same muss fehlschlagen, wenn root einen Knoten an einer Stelle hat, an der subRoot eine leere Stelle hat.
Beim ersten Knoten mit dem richtigen Wert aufhören. Im dritten Beispiel schlägt die Wurzel 5 fehl, und das darunterliegende Blatt 5 stimmt überein.
Abschnitte der beiden Arrays vergleichen. Die Knoten eines Teilbaums verteilen sich über viele Ebenen, und jedes Array kann mit zusätzlichen -1-Einträgen enden. Ein Index hinter dem Ende ist eine leere Stelle, wie ein -1.
In Lua und R die Knotenindizes für die Rechnung 2*i+1 bei 0 beginnen lassen und root[i + 1] lesen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Subtree of Another Tree?

Ein Vergleich ab jedem Knoten kostet im schlimmsten Fall O(n·m), wobei n und m die Größen der beiden Bäume sind. Werden Vergleiche nur an Knoten durchgeführt, deren Höhe der Höhe von subRoot entspricht, sinkt der Aufwand auf O(n + m), da jeder Knoten von root dann höchstens einmal durchlaufen wird.

Kann „Teilbaum eines anderen Baums“ mit Zeichenfolgenabgleich gelöst werden?

Ja. Schreibe jeden Baum in Preorder-Notation, mit # für jedes leere Kind und einem Trennzeichen vor jedem Wert: ,2,1,#,#,3,#,#. subRoot ist genau dann ein Teilbaum, wenn seine Zeichenfolge in der Zeichenfolge von root vorkommt, und KMP findet sie in O(n + m). Ohne die Markierungen ergeben verschiedene Formen dieselbe Zeichenfolge; ohne Trennzeichen enthält 12 die 2.

Zählt ein Knoten, der subRoot entspricht, aber zusätzliche Kinder hat?

Nein. Ein Teilbaum ist ein Knoten zusammen mit all seinen Nachkommen, daher muss auch jeder Knoten unter dem Treffer in subRoot vorkommen. Im zweiten Beispiel macht die zusätzliche 0 unter der 3 die Antwort zu false.

def isSubtree(root, subRoot):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

true