Symmetric Tree

Q: Wie hoch ist die Zeitkomplexität eines symmetrischen Baums?

Jeder tatsächliche Knoten wird genau einmal verglichen, als Teil eines gespiegelten Paares, daher beträgt die Laufzeit O(n) . Die rekursive und die Stack-Version benötigen zusätzlichen Speicherplatz von O(h) für die noch ausstehenden Paare entlang des aktuellen Pfads. Die Version, die Ebene für Ebene vorgeht, hält eine Ebene im Speicher: O(w) für die breiteste Ebene.

Q: Wie überprüfst du ohne Rekursion, ob ein Binärbaum symmetrisch ist?

Führe einen Stapel oder eine Warteschlange mit Knotenpaaren, die einander entsprechen müssen, beginnend mit den beiden Kindern der Wurzel. Nimm ein Paar heraus, brich bei einer Abweichung ab und füge das äußere Paar sowie das innere Paar ihrer Kinder hinzu. Wenn der Stapel leer ist, ohne dass eine Abweichung festgestellt wurde, ist der Baum symmetrisch.

Q: Was ist der Unterschied zwischen einem symmetrischen Baum und zwei identischen Bäumen?

Zwei Bäume sind identisch, wenn du links mit links und rechts mit rechts vergleichst. Ein Baum ist symmetrisch, wenn sein linker Teilbaum mit dem Spiegelbild seines rechten Teilbaums identisch ist. Dabei werden die Seiten über Kreuz verglichen: links mit rechts und rechts mit links. Derselbe Code zum Vergleichen der Knotenpaare löst beide Probleme, wenn die Kindpaare vertauscht werden.

Q: Ist ein Baum mit einem einzelnen Knoten symmetrisch?

Ja. Ein einzelner Knoten hat zwei leere Kindpositionen, und zwei leere Positionen spiegeln einander. Eine Wurzel mit genau einem Kind ist niemals symmetrisch, da dieses Kind einer leeren Position gegenübersteht.

LeichtBaumdurchlauf

+10

Du erhältst einen binären Baum, der im Level-Order-Verfahren im Array tree gespeichert ist. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich an den Indizes 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet eine leere Stelle und das Array kann mit zusätzlichen -1-Einträgen enden. Gib true zurück, wenn der Baum spiegelsymmetrisch zu einer vertikalen Linie durch die Wurzel ist, andernfalls false. Sowohl die Form als auch die Werte müssen übereinstimmen.

Funktion

isSymmetric(tree: integer-array) → boolean

treeinteger-array: den Binärbaum in Ebenenreihenfolge, wobei -1 eine leere Stelle kennzeichnet
Gibt zurückboolean: true, wenn der Baum sich selbst spiegelt, andernfalls false

Einschränkungen

1 ≤ tree.length ≤ 32767
Jedes tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 1000.
tree[0] ist niemals -1, also hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten mit zusätzlichen -1-Einträgen enden.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und die Tiefe beträgt höchstens 14.

Beispiele

Eingabe: tree = [1, 2, 2, 3, 4, 4, 3]
Ausgabe: true
Erklärung: Klappe den Baum in der Mitte zusammen. Die beiden 2 an den Indizes 1 und 2 treffen aufeinander, die äußeren 3 an den Indizes 3 und 6 treffen aufeinander, und die inneren 4 bei 4 und 5 treffen aufeinander.

Eingabe: tree = [1, 2, 2, -1, 3, -1, 3]
Ausgabe: false
Erklärung: Beide 3er hängen rechts von ihren Eltern. In einem Spiegelbild muss das rechte Kind der linken 2 (Index 4) dem linken Kind der rechten 2 (Index 5) zugewandt sein, und Index 5 ist leer.

Eingabe: tree = [4, 6, 6, 5, -1, -1, 9]
Ausgabe: false
Erklärung: Die Form ist spiegelbildlich: Index 3 steht Index 6 gegenüber, und beide enthalten einen Knoten. Ihre Werte unterscheiden sich: 5 gegenüber 9, daher ist der Baum nicht symmetrisch.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn die Form sich selbst spiegelt, aber einige Werte nicht übereinstimmen: Wie viele Knotenwerte musst du mindestens ändern, damit der Baum symmetrisch wird?

Tipps

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

0 von 3 geöffnet

Lösung

Symmetrie ist eine Eigenschaft von Paaren. Jeder Knoten hat auf der anderen Seite der Wurzel einen Partner an der spiegelbildlichen Position, und der Partner eines linken Kindes ist ein rechtes Kind. Du vergleichst also nie einen Knoten mit seinen eigenen Kindern: Du durchläufst gleichzeitig die beiden Hälften des Baums in entgegengesetzte Richtungen, vergleichst bei jedem Paar Form und Wert und hörst beim ersten Paar auf, bei dem sie nicht übereinstimmen.

Vergleiche jede Ebene mit ihrer Umkehrung

Idee

Zuerst: So bewegst du dich im Array. Der Knoten am Index i hat sein linkes Kind am Index 2*i+1 und sein rechtes Kind am Index 2*i+2. Ein Kind ist nur dann real, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [1, 2, 2, 3, 4, 4, 3] hat die Wurzel 1 ihre Kinder an den Indizes 1 und 2, und die 2 am Index 1 hat ihre Kinder an den Indizes 3 und 4.

Betrachte nun den Baum Ebene für Ebene. Ein Spiegelbild ist von links nach rechts genauso zu lesen wie von rechts nach links. Daher muss jede Ebene, einschließlich ihrer leeren Stellen, in beide Richtungen gleich gelesen werden. Im ersten Beispiel lauten die Ebenen unterhalb der Wurzel 2 2 und 3 4 4 3. Im zweiten Beispiel lauten sie 2 2 und anschließend -1 3 -1 3. Umgekehrt gelesen ergibt das 3 -1 3 -1, also ist das Ergebnis false.

Die leeren Stellen müssen in der Zeile bleiben. Ohne sie würde die unterste Ebene des zweiten Beispiels 3 3 lauten und den Test bestehen. Schreibe für jede Kindposition jedes realen Knotens auf der Ebene einen Eintrag, bei einer leeren Position -1; auch die Kinder leerer Positionen sind leer und tragen daher nichts bei. Jeder Knoten wird einmal besucht, daher beträgt die Laufzeit O(n). Es wird jeweils eine Ebene im Speicher gehalten, also O(w) für die breiteste Ebene w.

Algorithmus

Beginne mit einer Liste, die den Wurzelindex 0 enthält.
Schreibe für jeden Index in der Liste von links nach rechts beide Positionen der Kinder auf: den Wert des Kindes, wenn es tatsächlich vorhanden ist, andernfalls -1. Sammle die tatsächlich vorhandenen Kinder für die nächste Ebene.
Wenn sich diese Zeile mit den Kinderpositionen von ihrer Umkehrung unterscheidet, gib false zurück.
Gehe zur nächsten Ebene und wiederhole den Vorgang, bis sie leer ist, und gib dann true zurück.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Rekursion bei gespiegelten Paaren

Idee

Vergleiche statt ganzer Ebenen zwei Teilbäume: den linken Teilbaum der Wurzel, der bei Index 1 beginnt, und den rechten Teilbaum, der bei Index 2 beginnt. Zwei Positionen spiegeln einander, wenn beide leer sind oder wenn beide denselben Wert enthalten und ihre Kinder über Kreuz übereinstimmen. Das linke Kind des einen spiegelt das rechte Kind des anderen (das äußere Paar), und das rechte Kind des einen spiegelt das linke Kind des anderen (das innere Paar).

Im ersten Beispiel vergleicht mirrors(1, 2) die beiden 2er und ruft dann mirrors(3, 6) für die äußeren 3er und mirrors(4, 5) für die inneren 4er auf. Bei jedem dieser Aufrufe befinden sich darunter nur leere Positionen, daher wird true zurückgegeben. Im zweiten Beispiel findet mirrors(4, 5) an Index 4 eine 3, der an Index 5 eine leere Position gegenübersteht. Der Aufruf gibt false zurück, und das false wird bis zur Wurzel weitergereicht.

Jeder echte Knoten gehört zu höchstens einem Paar, daher beträgt die Laufzeit O(n). Der Aufrufstapel ist so tief wie der Baum, also O(h), was hier höchstens 14 Frames sind.

Algorithmus

Schreibe mirrors(a, b). Eine Position ist leer, wenn ihr Index hinter dem Ende liegt oder sie den Wert -1 enthält. Wenn beide Positionen leer sind, gib true zurück; wenn nur eine leer ist, gib false zurück.
Wenn sich tree[a] und tree[b] unterscheiden, gib false zurück.
Andernfalls gib mirrors(2*a+1, 2*b+2) und mirrors(2*a+2, 2*b+1) zurück.
Gib mirrors(1, 2) zurück. Eine Wurzel ohne Kinder ergibt zwei leere Positionen, was true ist.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Expliziter Stapel gespiegelter Paare

Idee

Die Rekursion benötigt nur eines: die Paare, die noch überprüft werden müssen. Lege diese Paare auf einen eigenen Stapel, und die Aufrufe entfallen. Beginne mit dem Paar (1, 2). Nimm ein Paar vom Stapel. Wenn beide Stellen leer sind, gibt es darunter nichts, also fahre fort. Wenn eine Stelle leer ist oder die Werte unterschiedlich sind, ist der Baum nicht symmetrisch. Andernfalls lege das äußere Paar (2*a+1, 2*b+2) und das innere Paar (2*a+2, 2*b+1) auf den Stapel.

Die Reihenfolge, in der du die Paare überprüfst, spielt keine Rolle, denn der Baum ist nur dann symmetrisch, wenn jedes Paar übereinstimmt. Ein Stapel ergibt eine Tiefensuche; eine Warteschlange würde eine Suche nach Ebenen ergeben und genauso funktionieren. Das dritte Beispiel endet beim ersten fehlerhaften Paar (3, 6), das 5 und 9 enthält.

Jedes Entfernen vom Stapel verarbeitet ein Paar, und jeder echte Knoten kommt in höchstens einem Paar vor, also beträgt die Laufzeit O(n). Der Stapel enthält ungefähr ein ausstehendes Paar pro Ebene des aktuellen Pfads, benötigt also O(h) Speicher, und du musst dir keine Gedanken über ein Rekursionslimit machen.

Algorithmus

Lege das Paar (1, 2) auf einen Stack.
Nimm ein Paar (a, b) vom Stack. Wenn beide Stellen leer sind (Index hinter dem Ende oder -1), fahre mit dem nächsten Paar fort.
Wenn nur eine Stelle leer ist oder tree[a] sich von tree[b] unterscheidet, gib false zurück.
Lege (2*a+1, 2*b+2) und (2*a+2, 2*b+1) auf den Stack.
Wenn der Stack leer ist, gib true zurück.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Stolperfallen und Grenzfälle

Die meisten falschen Antworten vergleichen das falsche Knotenpaar oder vergessen, dass eine leere Stelle Teil der Form ist.

Jeden Teilbaum für sich überprüfen. Der linke Teilbaum muss nicht für sich symmetrisch sein: In [1, 2, 2, 3, 4, 4, 3] ist der Teilbaum 2, 3, 4 es nicht, der ganze Baum aber schon. Er muss den rechten Teilbaum spiegeln.
Die Kinder falsch paaren. Das linke Kind der einen Seite liegt dem rechten Kind der anderen gegenüber: (2*a+1, 2*b+2) und (2*a+2, 2*b+1), niemals (2*a+1, 2*b+1).
Nur Werte vergleichen. Entfernt man die leeren Stellen aus [1, 2, 2, -1, 3, -1, 3], liest sich jede Ebene in beide Richtungen gleich, und doch ist der Baum nicht symmetrisch. Behalte -1 in einer Zeile der Ebene bei oder überprüfe im Paartest, ob die Stellen leer sind.
Über das Ende hinaus lesen. Ein Index jenseits des Array-Endes entspricht einer leeren Stelle. Überprüfe a < n, bevor du tree[a] liest; ein Baum mit nur einem Knoten hat überhaupt keinen Index 1 oder 2.
Nach dem ersten passenden Paar aufhören. Ein gutes Paar beweist nichts; gib erst true zurück, nachdem jedes Paar überprüft wurde.
Den Offset in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte die Knotenindizes für die 2*i+1-Arithmetik bei 0 und lies tree[i + 1].

Häufige Fragen4

Wie hoch ist die Zeitkomplexität eines symmetrischen Baums?

Jeder tatsächliche Knoten wird genau einmal verglichen, als Teil eines gespiegelten Paares, daher beträgt die Laufzeit O(n). Die rekursive und die Stack-Version benötigen zusätzlichen Speicherplatz von O(h) für die noch ausstehenden Paare entlang des aktuellen Pfads. Die Version, die Ebene für Ebene vorgeht, hält eine Ebene im Speicher: O(w) für die breiteste Ebene.

Wie überprüfst du ohne Rekursion, ob ein Binärbaum symmetrisch ist?

Führe einen Stapel oder eine Warteschlange mit Knotenpaaren, die einander entsprechen müssen, beginnend mit den beiden Kindern der Wurzel. Nimm ein Paar heraus, brich bei einer Abweichung ab und füge das äußere Paar sowie das innere Paar ihrer Kinder hinzu. Wenn der Stapel leer ist, ohne dass eine Abweichung festgestellt wurde, ist der Baum symmetrisch.

Was ist der Unterschied zwischen einem symmetrischen Baum und zwei identischen Bäumen?

Zwei Bäume sind identisch, wenn du links mit links und rechts mit rechts vergleichst. Ein Baum ist symmetrisch, wenn sein linker Teilbaum mit dem Spiegelbild seines rechten Teilbaums identisch ist. Dabei werden die Seiten über Kreuz verglichen: links mit rechts und rechts mit links. Derselbe Code zum Vergleichen der Knotenpaare löst beide Probleme, wenn die Kindpaare vertauscht werden.

Ist ein Baum mit einem einzelnen Knoten symmetrisch?

Ja. Ein einzelner Knoten hat zwei leere Kindpositionen, und zwei leere Positionen spiegeln einander. Eine Wurzel mit genau einem Kind ist niemals symmetrisch, da dieses Kind einer leeren Position gegenübersteht.

Python

def isSymmetric(tree):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

tree = [1, 2, 2, 3, 4, 4, 3]

Erwartet

true

Symmetric Tree

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergleiche jede Ebene mit ihrer Umkehrung

Rekursion bei gespiegelten Paaren

Expliziter Stapel gespiegelter Paare

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben