Binary Tree Level Order Traversal

Q: Wie hoch ist die Zeitkomplexität der Ebenenreihenfolge-Durchquerung eines binären Baums?

Sowohl die Breitensuche als auch die Tiefensuche besucht jeden Knoten einmal, sodass sie bei n Knoten in O(n) Zeit ausgeführt werden. Die Antwort selbst enthält n Werte, daher beträgt der Speicherbedarf O(n) . Darüber hinaus enthält die Warteschlange höchstens ungefähr so viele Elemente wie die breiteste Ebene, und die Rekursion ist höchstens so tief wie der Baum.

Q: Woher weißt du, wo eine Ebene bei einer Breitensuche endet?

Lies die Größe der Warteschlange zu Beginn jeder Runde aus. In diesem Moment enthält die Warteschlange genau die Knoten einer Ebene, sodass das Herausnehmen dieser Anzahl von Knoten genau die Ebene und nichts weiter entfernt. Zwei weitere Möglichkeiten funktionieren ebenfalls: Halte die aktuelle Ebene und die nächste Ebene in zwei getrennten Listen oder füge nach jeder Ebene eine Markierung hinzu.

Q: Kann eine Traversierung in Ebenenreihenfolge mit Tiefensuche durchgeführt werden?

Ja. Übergib jedem Knoten seine Tiefe und füge seinen Wert der Liste für diese Tiefe hinzu. Solange der Durchlauf den linken Teilbaum vor dem rechten besucht, ist jede Liste am Ende von links nach rechts geordnet. Das ist ebenfalls O(n) ; die Breitensuche passt direkter, weil sie die Ebenen der Reihe nach erzeugt.

Q: Das Array ist bereits Ebene für Ebene gespeichert. Warum lesen wir es nicht in Abschnitten?

Für dieses Format funktioniert Folgendes: Ebene d belegt die Indizes 2^d-1 bis 2^(d+1)-2 . Daher kannst du die nicht leeren Werte jedes Bereichs sammeln und beim ersten Bereich ohne Werte aufhören. In einem Vorstellungsgespräch besteht der Baum jedoch normalerweise aus Knotenobjekten mit Zeigern nach links und rechts und ohne Indizes, nach denen man schneiden könnte. Die Warteschlangen-basierte Traversierung lässt sich auf diese Form und auf Varianten wie die Zickzack-Reihenfolge oder die Ansicht von der rechten Seite übertragen.

MittelBaumdurchlauf Warteschlange

+10

Du erhältst einen Binärbaum, der im Array tree gespeichert ist. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich bei 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 die Knotenwerte Ebene für Ebene zurück: eine Liste mit dem Wert der Wurzel, dann eine Liste mit den Werten eine Ebene weiter unten, von links nach rechts, und so weiter bis zur tiefsten Ebene.

Funktion

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: der Baum in Heap-Reihenfolge, mit -1 für eine leere Stelle
Gibt zurückinteger-2d-array: eine Liste von Werten pro Ebene, zuerst die oberste Ebene, jeweils von links nach rechts

Einschränkungen

1 ≤ tree.length ≤ 32767
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 zusätzliche -1-Einträge enthalten.
Auch die beiden Kinder eines leeren Feldes sind leer, und die Tiefe beträgt höchstens 14.

Beispiele

Eingabe: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Ausgabe: [[4], [9, 2], [6, 8, 5], [3]]
Erklärung: Die Wurzel 4 hat die Kinder 9 und 2 an den Indizes 1 und 2. Index 3 ist leer, daher ist die dritte Ebene 6 (Index 4, unter 9), dann 8 und 5 (Indizes 5 und 6, unter 2). Die 3 an Index 9 ist das linke Kind von 6 und steht allein auf der vierten Ebene.

Eingabe: tree = [7, -1, -1]
Ausgabe: [[7]]
Erklärung: Beide Kinder der Wurzel sind -1, daher besteht der Baum aus dem einzelnen Knoten 7 und hat eine Ebene.

Eingabe: tree = [1, 3, -1, 5, -1, -1, -1]
Ausgabe: [[1], [3], [5]]
Erklärung: Jeder Knoten hat nur ein linkes Kind: 3 an Index 1 und 5 an Index 3. Jede Ebene enthält einen Wert, und die nachfolgenden -1-Einträge fügen nichts hinzu.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die Ebenen in Zickzack-Reihenfolge zurückgeben, die erste von links nach rechts, die zweite von rechts nach links und so weiter, ohne eine Ebene zu sortieren?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Ebene muss als eigene Liste ausgegeben werden, geordnet von links nach rechts. Eine Breitensuche mit einer Warteschlange besucht die Knoten genau in dieser Reihenfolge. Die zusätzliche Idee besteht darin, zu erkennen, wo eine Ebene endet: Zu Beginn jeder Runde enthält die Warteschlange die gesamte aktuelle Ebene und nichts anderes, daher gibt ihre Größe an, wie viele Knoten du entnehmen musst. Auch eine Tiefensuche funktioniert, solange sie die Tiefe jedes Knotens mitführt und zuerst nach links und dann nach rechts geht.

Tiefensuche, nach Tiefe geordnet

Idee

Bewegen wir uns zunächst im Array. Das linke Kind am Index i befindet sich bei 2i+1 und das rechte Kind bei 2i+2. Ein Kind fehlt, wenn sein Index außerhalb des Arrays liegt oder den Wert -1 enthält. In Beispiel 1 befinden sich die Kinder von 9 (Index 1) an den Indizes 3 und 4, die -1 beziehungsweise 6 enthalten; 9 hat also nur ein rechtes Kind.

Durchlaufe den Baum nun tiefenorientiert und übergib jedem Knoten seine Tiefe, wobei die Wurzel die Tiefe 0 hat. Lege für jede Tiefe eine Liste an. Wenn du einen Knoten auf Tiefe d erreichst, hänge seinen Wert an die Liste d an. Gibt es bisher nur d Listen, ist dies der erste Knoten auf einer neuen Ebene, also lege zuerst eine neue Liste an.

Warum ergibt sich jede Ebene von links nach rechts? Der Durchlauf beendet den gesamten linken Teilbaum eines Knotens, bevor er den rechten Teilbaum betritt. Betrachte zwei Knoten auf derselben Ebene: An der Stelle, an der sich ihre Pfade von der Wurzel aus trennen, führt einer nach links und einer nach rechts, und der Durchlauf erreicht den linken zuerst. In Beispiel 1 lautet die Reihenfolge 4, 9, 6, 3, 2, 8, 5; dadurch werden die Listen mit [4], [9, 2], [6, 8, 5], [3] gefüllt.

Jeder Knoten wird einmal besucht, daher beträgt die Laufzeit für n Knoten O(n), und die Listen enthalten insgesamt n Werte. Die Rekursion ist nur so tief wie der Baum, hier also höchstens 15 Ebenen. Die R-Version verwendet stattdessen einen expliziten Stack. Dabei wird zuerst das rechte Kind und dann das linke Kind auf den Stack gelegt, sodass das linke zuerst entnommen wird. Anschließend werden die Werte mit split nach Tiefe gruppiert.

Algorithmus

Erstelle eine leere Liste von Ebenen.
Besuche die Wurzel mit Tiefe 0.
Halte bei Knoten i mit Tiefe d an, wenn i hinter dem Ende liegt oder tree[i] -1 ist.
Wenn es nur d Listen gibt, füge eine leere hinzu. Hänge tree[i] an Liste d an.
Besuche 2i+1 und dann 2i+2, beide mit Tiefe d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Breitensuche, eine Ebene pro Runde

Idee

Eine Warteschlange gibt Werte in der Reihenfolge zurück, in der sie hineingekommen sind. Füge die Wurzel ein. Nimm dann wiederholt einen Knoten heraus und füge seine Kinder ein, zuerst das linke Kind. Jeder Knoten auf Ebene d+1 kommt in die Warteschlange, wenn sein Elternknoten auf Ebene d sie verlässt. Daher werden alle Knoten auf Ebene d herausgenommen, bevor ein Knoten auf Ebene d+1 herausgenommen wird, und innerhalb einer Ebene werden die Knoten von links nach rechts herausgenommen.

So erhältst du einen Strom von Werten in Ebenenreihenfolge. Um ihn in Ebenen aufzuteilen, lies zu Beginn einer Runde die Größe der Warteschlange ab. In diesem Moment enthält die Warteschlange genau die aktuelle Ebene: Die vorherige Ebene ist abgearbeitet, und noch kein Knoten der nächsten Ebene ist hinzugekommen. Nimm so viele Knoten heraus und füge sie einer Liste hinzu. Die Kinder, die sie hinzufügen, gehören zur nächsten Runde.

In Beispiel 1 beginnt die Warteschlange mit [4]: Nimm 1 Knoten heraus, Zeile [4], und 9, 2 kommen hinzu. Nimm 2 Knoten heraus, Zeile [9, 2], und 6, 8, 5 kommen hinzu. Nimm 3 heraus, Zeile [6, 8, 5], und 3 kommt hinzu. Nimm 1 heraus, Zeile [3], und die Warteschlange ist leer.

Jeder Knoten kommt einmal in die Warteschlange und wird einmal herausgenommen, daher beträgt die Laufzeit O(n). Die Warteschlange enthält höchstens ungefähr so viele Knoten wie eine Ebene, bis zu 16384 Knoten auf der tiefsten Ebene eines vollständigen Baums der Tiefe 14. Verwende eine echte Warteschlange oder einen Kopfindex: In vielen Sprachen verschiebt das Herausnehmen des ersten Elements aus einer gewöhnlichen Array-Liste alle nachfolgenden Elemente.

Algorithmus

Füge den Index der Wurzel 0 zu einer Warteschlange hinzu.
Solange die Warteschlange nicht leer ist, lies ihre Größe s aus und beginne eine leere Zeile.
Nimm s Indizes heraus. Füge für jeden Index i tree[i] zur Zeile hinzu.
Füge 2i+1 und dann 2i+2 zur Warteschlange hinzu, wenn der Index innerhalb des Arrays liegt und nicht den Wert -1 enthält.
Füge die Zeile zur Antwort hinzu und beginne die nächste Runde.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Stolperfallen und Grenzfälle

Die Traversierung selbst ist kurz. Die Fehler liegen bei den Ebenengrenzen und den leeren Stellen.

Die Größe der Warteschlange auslesen, während du sie noch leerst. In einer Schleife wie while (j < queue.length) wächst die Länge, wenn Kinder hinzukommen, sodass die nächste Ebene in die aktuelle Zeile rutscht. Lies die Größe einmal aus, bevor die Runde beginnt.
Das rechte Kind vor dem linken hinzufügen. Dann wird jede Ebene von rechts nach links ausgegeben. Dasselbe gilt für eine Tiefensuche, die zuerst den rechten Teilbaum besucht.
-1 als Wert behandeln. Eine leere Stelle ist kein Knoten, kommt also nie in eine Zeile und nie in die Warteschlange.
Die Bereichsprüfung vergessen. Die Kinder der tiefsten Knoten können hinter dem Ende des Arrays liegen. Prüfe daher child < n, bevor du tree[child] ausliest.
Leere Ebenen zurückgeben. Die abschließenden -1-Einträge enthalten keine Knoten, daher lautet die Antwort für [7, -1, -1] [[7]] und nicht [[7], []].

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der Ebenenreihenfolge-Durchquerung eines binären Baums?

Sowohl die Breitensuche als auch die Tiefensuche besucht jeden Knoten einmal, sodass sie bei n Knoten in O(n) Zeit ausgeführt werden. Die Antwort selbst enthält n Werte, daher beträgt der Speicherbedarf O(n). Darüber hinaus enthält die Warteschlange höchstens ungefähr so viele Elemente wie die breiteste Ebene, und die Rekursion ist höchstens so tief wie der Baum.

Woher weißt du, wo eine Ebene bei einer Breitensuche endet?

Lies die Größe der Warteschlange zu Beginn jeder Runde aus. In diesem Moment enthält die Warteschlange genau die Knoten einer Ebene, sodass das Herausnehmen dieser Anzahl von Knoten genau die Ebene und nichts weiter entfernt. Zwei weitere Möglichkeiten funktionieren ebenfalls: Halte die aktuelle Ebene und die nächste Ebene in zwei getrennten Listen oder füge nach jeder Ebene eine Markierung hinzu.

Kann eine Traversierung in Ebenenreihenfolge mit Tiefensuche durchgeführt werden?

Ja. Übergib jedem Knoten seine Tiefe und füge seinen Wert der Liste für diese Tiefe hinzu. Solange der Durchlauf den linken Teilbaum vor dem rechten besucht, ist jede Liste am Ende von links nach rechts geordnet. Das ist ebenfalls O(n); die Breitensuche passt direkter, weil sie die Ebenen der Reihe nach erzeugt.

Das Array ist bereits Ebene für Ebene gespeichert. Warum lesen wir es nicht in Abschnitten?

Für dieses Format funktioniert Folgendes: Ebene d belegt die Indizes 2^d-1 bis 2^(d+1)-2. Daher kannst du die nicht leeren Werte jedes Bereichs sammeln und beim ersten Bereich ohne Werte aufhören. In einem Vorstellungsgespräch besteht der Baum jedoch normalerweise aus Knotenobjekten mit Zeigern nach links und rechts und ohne Indizes, nach denen man schneiden könnte. Die Warteschlangen-basierte Traversierung lässt sich auf diese Form und auf Varianten wie die Zickzack-Reihenfolge oder die Ansicht von der rechten Seite übertragen.

Python

def levelOrder(tree):
    # Schreibe hier deinen Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

[[4], [9, 2], [6, 8, 5], [3]]