Binary Tree Level Order Traversal

Q: Wie hoch ist die zeitliche Komplexität der Ebenen-Reihenfolge-Durchquerung eines Binärbaums?

Beide Lösungen besuchen jeden Knoten einmal: O(n) Zeit für n Knoten. Die Antwort enthält n Werte, daher beträgt der Speicherbedarf O(n) . Darüber hinaus enthält die Warteschlange ungefähr so viele Elemente wie die breiteste Ebene und die Rekursion so viele wie die Höhe des Baums.

Q: Woran erkennst du bei einer Breitensuche, wo eine Ebene endet?

Lies zu Beginn jeder Runde die Größe der Warteschlange aus und entnimm genau so viele Knoten. Zwei andere Methoden funktionieren ebenfalls: Bewahre die aktuelle Ebene und die nächste Ebene in zwei getrennten Listen auf oder füge nach jeder Ebene einen Markierer in die Warteschlange ein.

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

Für dieses Format funktioniert es so: Die Ebene d mit der Wurzel bei 0 füllt die Indizes 2^d-1 bis 2^(d+1)-2 . Sammle also die nicht leeren Werte jedes Bereichs, bis ein Bereich keine mehr enthält. Bei Vorstellungsgesprächen werden stattdessen meist Knotenobjekte mit Zeigern übergeben; nur die Warteschlange lässt sich auf diese Form übertragen.

MittelBaumdurchlauf Warteschlange

+10

Das Array tree enthält einen Binärbaum. 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 am Ende können zusätzliche -1-Einträge stehen.

Gib die Knotenwerte Ebene für Ebene zurück: eine Liste pro Ebene, von der Wurzel bis zur tiefsten Ebene, jeweils mit den Werten von links nach rechts.

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, beginnend mit der obersten 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, also hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten mit zusätzlichen -1-Einträgen enden.
Auch beide Kinder eines leeren Platzes 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: Index 3 ist leer, daher hat 9 nur ein rechtes Kind, 6. Die dritte Ebene besteht aus 6, 8, 5, und die 3 an Index 9, unterhalb von 6, ist 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 abschließenden -1-Einträge fügen nichts hinzu.

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 von links nach rechts ausgegeben werden. Eine Breitensuche mit einer Warteschlange besucht die Knoten in dieser Reihenfolge, und zu Beginn jeder Runde enthält die Warteschlange genau eine Ebene, sodass ihre Größe angibt, wie viele Knoten zu entnehmen sind. Auch eine Tiefensuche, die die Tiefe jedes Knotens erfasst, funktioniert.

Tiefensuche, nach Tiefe abgelegt

Idee

Durchlaufe den Baum in der Tiefe zuerst, übergib jedem Knoten seine Tiefe (0 für die Wurzel) und führe für jede Tiefe eine eigene Liste. Ein Knoten mit der Tiefe d fügt seinen Wert zur Liste d hinzu und legt diese Liste an, wenn er der erste Knoten auf dieser Ebene ist.

Jede Liste ergibt sich von links nach rechts, da der Durchlauf zuerst den linken Teilbaum eines Knotens vollständig durchläuft, bevor er den rechten betritt. Von zwei Knoten auf derselben Ebene wird derjenige zuerst erreicht, dessen Pfad an der Stelle, an der sich die Pfade trennen, nach links abbiegt. In Beispiel 1 füllt die Besuchsreihenfolge 4, 9, 6, 3, 2, 8, 5 die Listen [4], [9, 2], [6, 8, 5], [3].

Jeder Knoten wird einmal besucht: Laufzeit O(n), mit einer Rekursionstiefe so groß wie die des Baums, höchstens 14 Ebenen.

Algorithmus

Erstelle eine leere Liste von Ebenen.
Besuche die Wurzel mit Tiefe 0.
Beende bei Knoten i mit Tiefe d, wenn i außerhalb des Bereichs liegt oder tree[i] gleich -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

Nimm einen Knoten aus der Warteschlange und füge seine Kinder ein, zuerst links. Ebene d+1 kommt erst hinzu, wenn Ebene d sie verlässt. Daher verlassen die Knoten die Warteschlange Ebene für Ebene, von links nach rechts.

Um diesen Strom in Ebenen aufzuteilen, lies die Größe der Warteschlange zu Beginn einer Runde ab. Die vorherige Ebene ist verschwunden und von der nächsten ist noch nichts angekommen, daher enthält die Warteschlange genau die aktuelle Ebene. Nimm so viele Knoten in eine Zeile; ihre Kinder warten auf die nächste Runde. In Beispiel 1 nehmen die Runden 1, 2, 3 und 1 Knoten auf.

Jeder Knoten kommt genau einmal in die Warteschlange und verlässt sie genau einmal: Laufzeit O(n). Die Warteschlange enthält ungefähr eine Ebene, höchstens 8.192 Knoten auf der tiefsten Ebene eines vollständigen Baums mit 14 Ebenen.

Algorithmus

Füge den Index 0 der Wurzel in eine Warteschlange ein.
Solange die Warteschlange nicht leer ist, lies ihre Größe s aus und beginne eine leere Zeile.
Entnimm s Indizes. Hänge für jeden Index i tree[i] an die Zeile an.
Füge 2i+1 und dann 2i+2 zur Warteschlange hinzu, wenn der Index innerhalb des Arrays liegt und den Wert -1 nicht 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 Größe der Warteschlange auszulesen, während du sie leerst. In while (j < queue.length) wächst die Länge, wenn Kinder hinzukommen, sodass die nächste Ebene in die aktuelle Zeile rutscht.
Das rechte Kind vor dem linken hinzuzufügen oder zuerst den rechten Teilbaum zu besuchen. Die zweite Ebene von Beispiel 1 ergibt dann [2, 9].
Die Bereichsprüfung child < n zu überspringen. Die Kinder der tiefsten Knoten liegen hinter dem Ende des Arrays.
Elemente am Anfang einer einfachen Array-Liste zu entfernen, wodurch in vielen Sprachen jedes Mal die gesamte Warteschlange verschoben wird. Verwende eine echte Warteschlange oder einen Kopfindex.
-1 als Knoten zu behandeln. Er kommt nie in eine Zeile oder die Warteschlange: [7, -1, -1] ergibt [[7]], nicht [[7], []].

Häufige Fragen3

Wie hoch ist die zeitliche Komplexität der Ebenen-Reihenfolge-Durchquerung eines Binärbaums?

Beide Lösungen besuchen jeden Knoten einmal: O(n) Zeit für n Knoten. Die Antwort enthält n Werte, daher beträgt der Speicherbedarf O(n). Darüber hinaus enthält die Warteschlange ungefähr so viele Elemente wie die breiteste Ebene und die Rekursion so viele wie die Höhe des Baums.

Woran erkennst du bei einer Breitensuche, wo eine Ebene endet?

Lies zu Beginn jeder Runde die Größe der Warteschlange aus und entnimm genau so viele Knoten. Zwei andere Methoden funktionieren ebenfalls: Bewahre die aktuelle Ebene und die nächste Ebene in zwei getrennten Listen auf oder füge nach jeder Ebene einen Markierer in die Warteschlange ein.

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

Für dieses Format funktioniert es so: Die Ebene d mit der Wurzel bei 0 füllt die Indizes 2^d-1 bis 2^(d+1)-2. Sammle also die nicht leeren Werte jedes Bereichs, bis ein Bereich keine mehr enthält. Bei Vorstellungsgesprächen werden stattdessen meist Knotenobjekte mit Zeigern übergeben; nur die Warteschlange lässt sich auf diese Form übertragen.

def levelOrder(tree):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

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