Invert Binary Tree

+10

Du erhältst einen Binärbaum, der im Array tree in Ebenenreihenfolge gespeichert ist. Die Wurzel steht am Index 0, die Kinder des Knotens am Index i stehen bei 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet einen leeren Platz, und das Array kann mit zusätzlichen Einträgen -1 enden.

Invertiere den Baum: Vertausche bei jedem Knoten das linke und das rechte Kind, sodass der gesamte Baum zu seinem Spiegelbild wird. Gib den invertierten Baum in derselben Form zurück, ohne -1-Einträge am Ende.

Funktion

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

treeinteger-array: der Binärbaum in Ebenenreihenfolge, wobei -1 eine leere Stelle kennzeichnet
Gibt zurückinteger-array: der gespiegelte Baum in Ebenenreihenfolge, ohne abschließende -1-Einträge

Einschränkungen

1 ≤ tree.length ≤ 16383
Jedes tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 1000.
tree[0] ist niemals -1, daher 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 = [5, 3, 8, 1, 4, -1, 9]
Ausgabe: [5, 8, 3, 9, -1, 4, 1]
Erklärung: Die Kinder der Wurzel 3 und 8 tauschen die Plätze. Unter ihnen kommen die 1 und 4 unter 3 als 4 und 1 zurück, und 8, das zuvor nur ein rechtes Kind 9 hatte, hat es jetzt links.

Eingabe: tree = [2, 7, -1, 6]
Ausgabe: [2, -1, 7, -1, -1, -1, 6]
Erklärung: Die Kette 2, 7, 6 neigt sich nach links und ihr Spiegelbild nach rechts. Die 7 bewegt sich von Index 1 zu Index 2 und die 6 von Index 3 zu Index 6, daher ist die Antwort länger als die Eingabe, mit -1 an jeder leeren Stelle vor dem letzten Knoten.

Eingabe: tree = [1, -1, -1]
Ausgabe: [1]
Erklärung: Ein einzelner Knoten ist sein eigenes Spiegelbild. Die beiden Einträge -1 sind Auffüllwerte, und in der Antwort werden alle abschließenden -1 weggelassen.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du überprüfen, ob ein Baum sein eigenes Spiegelbild ist, indem du dieselben Indexpaarungen verwendest, aber keine umgekehrte Kopie erstellst?

Tipps

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

0 von 3 geöffnet

Lösung

Einen Baum zu spiegeln bedeutet, dass jeder Knoten seinen linken und rechten Teilbaum vertauscht, bis ganz nach unten. Bei Knotenobjekten ist das ein Tausch pro Knoten. In dieser Array-Darstellung entspricht der Platz eines Knotens seinem Index. Zwei Teilbäume zu vertauschen bedeutet also, jeden Knoten in ihnen zu verschieben. Der Weg dahin besteht darin, die Antwort in einem neuen Array aufzubauen und jeden Knoten direkt an seinen gespiegelten Index zu kopieren. Dazu werden bei einer Traversierung Indexpaare mitgeführt: wo sich der Knoten jetzt befindet und wohin er kommt.

Rekursion, die jeden Knoten an seinem gespiegelten Index platziert

Idee

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

Nun zum Spiegeln. Die Wurzel bleibt an Index 0. Der linke Teilbaum eines Knotens wird zum rechten Teilbaum seiner gespiegelten Kopie, und sein rechter Teilbaum wird zum linken. Wenn also der Knoten an Index src im Ergebnis an Index dst landet, landet sein linkes Kind bei 2*dst+2 und sein rechtes Kind bei 2*dst+1. Schreibe place(src, dst): Kopiere den Wert und rufe dann place(2*src+1, 2*dst+2) und place(2*src+2, 2*dst+1) auf. Ein leerer Platz führt sofort zur Rückkehr. Im ersten Beispiel landet die 3 an Index 1 bei 2, also landet ihr linkes Kind 1 bei 6 und ihr rechtes Kind 4 bei 5.

Ein Knoten wechselt nie seine Ebene, daher bleibt sein gespiegelter Index innerhalb derselben Ebene wie sein ursprünglicher Index. Runde die Länge auf ganze Ebenen auf (1, 3, 7, 15, ...), fülle so viele Plätze mit -1 und entferne am Ende die abschließenden -1-Einträge. Im zweiten Beispiel wird die Länge 4 auf 7 aufgerundet, wodurch Platz für die 6 an Index 6 bleibt.

Jeder Knoten wird einmal platziert, und die Ausgabe wird einmal aufgefüllt und gekürzt: O(n) Zeit für ein Array der Länge n. Die Ausgabe benötigt O(n) Speicher und der Aufrufstapel O(h), hier höchstens 14 Aufrufe, wodurch Rekursion bei diesem Problem sicher ist.

Algorithmus

Runde die Länge auf size = 2^k - 1 auf und fülle eine Ausgabe dieser Größe mit -1.
Schreibe place(src, dst): Wenn src hinter dem Ende liegt oder tree[src] -1 ist, kehre zurück.
Setze andernfalls out[dst] = tree[src], rufe dann place(2*src+1, 2*dst+2) und place(2*src+2, 2*dst+1) auf.
Rufe place(0, 0) auf, entferne die abschließenden -1-Einträge und gib die Ausgabe zurück.

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]

Breitensuche mit einer Warteschlange von Indexpaaren

Idee

Dieselben Paare funktionieren auch ohne Rekursion. Lege (0, 0) in eine Warteschlange: die Wurzel und die Position, an die sie kommt. Nimm ein Paar (src, dst) vom Anfang der Warteschlange, kopiere tree[src] nach out[dst] und füge jedes vorhandene Kind mit seinem vertauschten Ziel hinzu: das linke Kind 2*src+1 mit 2*dst+2, das rechte Kind 2*src+2 mit 2*dst+1.

Das ist die klassische iterative Spiegelung. Bei Knotenobjekten nimmst du einen Knoten aus der Warteschlange, vertauschst seine beiden Kinder und fügst sie der Warteschlange hinzu. Hier wird der Tausch stattdessen in den Zielindex geschrieben, weil sich in einem Array nicht zwei ganze Teilbäume in einem Schritt vertauschen lassen. Jeder vorhandene Knoten kommt genau einmal in die Warteschlange und führt dabei die genaue Position mit, an die er gehört. So enthält die Ausgabe am Ende jeden Knoten an seiner gespiegelten Position. Im ersten Beispiel ergeben sich die Paare (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

Der Zeitaufwand beträgt O(n). Die Warteschlange enthält höchstens eine Ebene und ein wenig mehr, also O(w) für die breiteste Ebene w, zusätzlich zur O(n)-Ausgabe. Es gibt keinen Aufrufstapel, der überlaufen könnte, daher lässt sich diese Version unverändert auf tiefe, zeigerbasierte Bäume übertragen.

Algorithmus

Runde die Länge auf eine ganze Anzahl von Ebenen auf und fülle eine Ausgabe dieser Größe mit -1.
Lege das Paar (0, 0) in eine Warteschlange.
Nimm ein Paar (src, dst) vom Anfang der Warteschlange und setze out[dst] = tree[src].
Füge für jedes Kind, das sich innerhalb des Arrays befindet und nicht -1 ist, (2*src+1, 2*dst+2) und (2*src+2, 2*dst+1) zur Warteschlange hinzu.
Wenn die Warteschlange leer ist, entferne die abschließenden -1-Einträge und gib die Ausgabe zurück.

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]

Stolperfallen und Grenzfälle

Die Spiegelung selbst ist kurz beschrieben. Die Fehler entstehen durch das Array: seine Größe, sein Ende und die Frage, was beim Vertauschen zweier Einträge tatsächlich verschoben wird.

tree[2*i+1] und tree[2*i+2] direkt vertauschen. Dadurch werden zwei Werte vertauscht, aber nicht die Teilbäume darunter. Wenn du im ersten Beispiel die Indizes 1 und 2 vertauschst, hängen 1 und 4 unter der 8.
Die Ausgabe so lang wie die Eingabe machen. Ein gespiegelter Knoten kann hinter dem letzten Index der Eingabe landen, wie es bei der 6 im zweiten Beispiel der Fall ist. Bemiss die Ausgabe anhand der vollständigen Ebenen.
Das Kürzen vergessen. Die Antwort endet ohne -1, sowohl bei aufgefüllten Eingaben als auch bei Bäumen, deren Spiegelung früher endet als die Eingabe.
Das ganze Array umkehren. Dadurch werden die Ebenen durcheinandergebracht: Das letzte Blatt würde zur Wurzel.
Die Bereichsprüfung überspringen. Ein Kindindex kann hinter dem Ende der Eingabe liegen, weil das Array direkt nach dem letzten Knoten enden kann.
Den Versatz in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte für die Berechnung mit 2*i+1 die Indizes bei 0 und lies tree[i + 1].

Häufige Fragen4

Was bedeutet es, einen Binärbaum umzukehren?

Das Invertieren eines Binärbaums erzeugt sein Spiegelbild: An jedem Knoten tauschen der linke und der rechte Teilbaum die Plätze. Die Wurzel bleibt, wo sie ist, das am weitesten links liegende Blatt wird zum am weitesten rechts liegenden, und eine linke Kette wird zu einer rechten Kette. Zweimaliges Invertieren ergibt wieder den ursprünglichen Baum.

Wie hoch ist die zeitliche Komplexität beim Invertieren eines binären Baums?

Jeder Knoten wird einmal besucht, daher beträgt die Laufzeit O(n). Eine rekursive Lösung benötigt für einen Baum mit der Tiefe h O(h) Stapelspeicher, eine Lösung mit einer Warteschlange benötigt für die breiteste Ebene O(w). In dieser Array-Version ist die Antwort selbst ein neues Array, was zusätzlich O(n) benötigt.

Wie invertiert man einen Binärbaum ohne Rekursion?

Verwende eine Warteschlange oder einen Stapel. Beginne an der Wurzel und vertausche jedes Mal, wenn du einen Knoten herausnimmst, dessen linkes und rechtes Kind und füge die Kinder hinzu. Jeder Knoten wird genau einmal vertauscht, unabhängig davon, in welcher Reihenfolge die Struktur ihn ausgibt. In der Array-Darstellung legst du stattdessen Paare von Indizes in die Warteschlange und schreibst jeden Knoten direkt an seine gespiegelte Position.

Warum kehrt das Invertieren eines binären Baums jede Ebene um?

Das Spiegeln vertauscht überall links und rechts, sodass die Knoten auf jeder Ebene in umgekehrter Reihenfolge erscheinen. Bei der Speicherung in Ebenenreihenfolge bedeutet das, dass der Array-Abschnitt jeder Ebene umgekehrt wird: Der Abschnitt [1, 4, -1, 9] aus dem ersten Beispiel ergibt [9, -1, 4, 1]. Jede Ebene umzukehren, nachdem die letzte mit -1 aufgefüllt wurde, ist eine dritte O(n)-Lösung, die nur bei diesem Array-Layout funktioniert.

Python

def invertTree(tree):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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