Construct Binary Tree from Preorder and Inorder Traversal

Q: Kannst du einen Binärbaum aus einer Preorder- und einer Postorder-Traversierung rekonstruieren?

Nicht allgemein. Die Preorder-Traversierung [1, 2] und die Postorder-Traversierung [2, 1] passen sowohl zu einem linken als auch zu einem rechten Kind, weil bei keiner der beiden Traversierungen die Wurzel zwischen ihren Teilbäumen steht. Das Paar reicht nur für einen vollen Binärbaum aus, in dem jeder Knoten null oder zwei Kinder hat.

MittelBaumdurchlauf Hashing Rekursion

+10

Du erhältst zwei Arrays, preorder und inorder, die die unterschiedlichen Werte desselben binären Baums auflisten. Bei der Preorder-Traversierung wird zuerst ein Knoten besucht, dann sein linker Teilbaum und anschließend sein rechter Teilbaum. Bei der Inorder-Traversierung wird zuerst der linke Teilbaum besucht, dann der Knoten und anschließend der rechte Teilbaum.

Baue den Baum wieder auf und gib ihn als Array in Ebenenreihenfolge zurück: die Wurzel an Index 0, die Kinder von Index i an den Indizes 2i+1 (links) und 2i+2 (rechts) sowie -1 für jede leere Stelle. Das Array endet beim letzten Knoten und enthält keine nachgestellten -1.

Funktion

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: die Werte in Preorder-Reihenfolge: Knoten, linker Teilbaum, rechter Teilbaum
inorderinteger-array: die Werte in Inorder-Reihenfolge: linker Teilbaum, Knoten, rechter Teilbaum
Gibt zurückinteger-array: den Baum in Ebenenreihenfolge, mit -1 für leere Stellen und ohne abschließendes -1

Einschränkungen

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, und alle Werte sind verschieden.
inorder enthält dieselben Werte, und beide Arrays beschreiben denselben Binärbaum.
Die Tiefe des Baums beträgt höchstens 14, daher ist jeder Index in der Antwort kleiner als 2¹⁴-1 = 16383.

Beispiele

Eingabe: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Ausgabe: [7, 3, 4, 0, 9, -1, 6]
Erklärung: Die Präorder beginnt mit der Wurzel 7. Sie befindet sich an der inorder-Position 3, daher kommen 0, 3, 9 nach links und 4, 6 nach rechts. 4 hat nur ein rechtes Kind, 6, daher bleibt der Index 5 bei -1.

Eingabe: preorder = [1, 2, 3]inorder = [2, 3, 1]
Ausgabe: [1, 2, -1, -1, 3]
Erklärung: Die Wurzel 1 steht in inorder ganz am Ende, also ist der Index 2 gleich -1. Von 2, 3 führt die Preorder-Auflistung zuerst 2 auf, und Inorder ordnet 3 dahinter ein, also ist 3 sein rechtes Kind am Index 4.

Weiterführende Frage

Kannst du den Baum ohne Rekursion in einem Durchlauf über preorder mit einem expliziten Stack neu aufbauen?

Tipps

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

0 von 3 geöffnet

Lösung

Preorder liefert die Wurzel jedes Teilbaums: den ersten Wert seines Abschnitts. Inorder liefert die Aufteilung: Werte vor der Wurzel kommen nach links, Werte danach nach rechts. Durch rekursives Vorgehen bei beiden Hälften wird der Baum wiederhergestellt, und eine Zuordnung von Werten zu ihren Positionen in der Inorder-Traversierung ermöglicht das Auffinden jeder Wurzel in einem Schritt.

Rekursiv aufteilen und nach der Wurzel suchen

Idee

Bei der Präorder-Traversierung folgt der linke Teilbaum auf seine Wurzel und benötigt einen Eintrag pro Wert, also m-lo Einträge, wobei m die Inorder-Position der Wurzel ist. Der rechte Teilbaum kommt danach, daher befindet sich seine Wurzel bei pre+1+(m-lo). Im ersten Beispiel enthält der linke Teil 0, 3, 9 drei Werte, also beginnt der rechte Teilbaum beim Präorder-Index 4, dem Wert 4.

Eine Tiefe von höchstens 14 hält jeden Ausgabeindex unter 2^14-1. Fülle so viele Zellen mit -1, schreibe jeden Wert an seinen Index und entferne am Ende die abschließenden -1-Einträge.

Das Durchsuchen jedes Inorder-Bereichs nach seiner Wurzel kostet O(n·h): Bereiche derselben Ebene überschneiden sich nicht, daher werden pro Ebene höchstens n Einträge durchsucht, hier also höchstens 14 × 3000 = 42000 Schritte. Ohne Tiefenbegrenzung ergibt ein baumförmiger Pfad eine Laufzeit von O(n²).

Algorithmus

Erzeuge out mit 2^14-1 Einträgen, die alle -1 sind.
Schreibe build(pre, lo, hi, h): Wenn lo > hi, gib zurück. Andernfalls schreibe preorder[pre] nach out[h].
Durchsuche inorder von lo aus, um die Position m der Wurzel zu finden. Der linke Teilbaum hat m-lo Werte.
Rufe build(pre+1, lo, m-1, 2*h+1) und build(pre+1+(m-lo), m+1, hi, 2*h+2) auf.
Rufe build(0, 0, n-1, 0) auf, entferne dann die nachgestellten -1-Einträge und gib den Rest zurück.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Rekursiv mit einer Positionszuordnung aufteilen

Idee

Die Werte sind verschieden, daher hat jeder genau eine Position in inorder. Halte diese vor Beginn der Rekursion in einer Zuordnung von Wert zu Position fest, und jede Suche nach einer Wurzel benötigt dann nur einen Schritt.

Das Erstellen der Zuordnung benötigt O(n), und jeder Wert wird anschließend einmal mit konstantem Aufwand platziert, sodass die Gesamtzeit O(n) beträgt. Die Zuordnung benötigt O(n) Speicherplatz, und die Rekursion einen Frame pro Ebene. In C und R sind die Werte höchstens 10^4, daher genügt ein einfaches Array mit 10^4+1 Einträgen als Zuordnung.

Algorithmus

Erstelle eine Zuordnung von jedem Wert in inorder zu seiner Position.
Erstelle out mit 2^14-1 Einträgen, die alle -1 sind.
Gib in build(pre, lo, hi, h) zurück, wenn lo > hi; andernfalls schreibe preorder[pre] in out[h] und suche seine Position m in der Zuordnung.
Führe rekursiv build(pre+1, lo, m-1, 2*h+1) und build(pre+1+(m-lo), m+1, hi, 2*h+2) aus.
Rufe build(0, 0, n-1, 0) auf, entferne dann die abschließenden -1-Einträge und gib den Rest zurück.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Stolperfallen und Grenzfälle

Den rechten Teilbaum bei pre+1+m statt bei pre+1+(m-lo) beginnen lassen. Das funktioniert, solange lo wie beim obersten Aufruf 0 ist, und schlägt fehl, sobald ein Bereich später beginnt.
Die Lücken weglassen. Ein fehlendes Kind belegt weiterhin seinen Platz, daher lautet die Antwort im zweiten Beispiel [1, 2, -1, -1, 3] und nicht [1, 2, 3].
Nachgestellte -1-Einträge stehen lassen. Gibt man alle 2^14-1 Zellen zurück, erhält das erste Beispiel 16376 zusätzliche -1-Einträge.
Bei jedem Aufruf Ausschnitte beider Arrays kopieren, was pro Ebene O(n) hinzufügt. Übergib Indexbereiche.
In Lua und R beginnen Arrays bei 1. Behalte für die Berechnungen 0-basierte Positionen bei und lies preorder[pre + 1] und out[h + 1].

Häufige Fragen3

Warum brauchst du sowohl die Preorder- als auch die Inorder-Traversierung, um einen binären Baum wiederherzustellen?

Die Vorordnung allein legt die Form nicht fest. Die Vorordnung [1, 2] passt zu einem Baum, in dem 2 das linke Kind von 1 ist, und zu einem, in dem es das rechte Kind ist. Die Inorder-Traversierung schafft Klarheit: [2, 1] platziert 2 links, [1, 2] rechts. Bei unterschiedlichen Werten beschreibt das Paar genau einen Baum.

Wie hoch ist die Zeitkomplexität beim Erstellen eines Binärbaums aus einer Vororder- und einer Inorder-Traversierung?

Mit einer Zuordnung von Werten zu ihrer Position in der Inorder-Reihenfolge beträgt der Zeitaufwand O(n) und der zusätzliche Speicherbedarf O(n). Ohne die Zuordnung kostet es O(n·h), jeden Inorder-Bereich nach seiner Wurzel zu durchsuchen. Bei einem baumförmigen Pfad steigt der Aufwand auf O(n²).

Kannst du einen Binärbaum aus einer Preorder- und einer Postorder-Traversierung rekonstruieren?

Nicht allgemein. Die Preorder-Traversierung [1, 2] und die Postorder-Traversierung [2, 1] passen sowohl zu einem linken als auch zu einem rechten Kind, weil bei keiner der beiden Traversierungen die Wurzel zwischen ihren Teilbäumen steht. Das Paar reicht nur für einen vollen Binärbaum aus, in dem jeder Knoten null oder zwei Kinder hat.

def buildTree(preorder, inorder):
    # Schreibe hier den Code

Test #1

Test #2

Argumente

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Erwartete Ausgabe

[7, 3, 4, 0, 9, -1, 6]