Binary Tree Right Side View

Q: Wie hoch sind die Zeit- und Speicherkomplexität der rechten Seitenansicht eines Binärbaums?

Die Laufzeit beträgt O(n) für n Knoten, und keine Lösung kann Knoten überspringen, da der rechteste Knoten einer Ebene an beliebiger Stelle hängen kann. Der Speicherbedarf beträgt O(w) für die Warteschlange, wobei w die breiteste Ebene ist, oder O(h) für die Suche zuerst nach rechts in einem Baum mit h Ebenen.

MittelBaumdurchlauf Warteschlange

+10

Das Array root enthält einen binären Baum. Die Wurzel befindet sich an Index 0, die Kinder des Knotens an Index i befinden sich an den Indizes 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.

Betrachte den Baum von der rechten Seite. Auf jeder Ebene siehst du genau einen Knoten, den am weitesten rechts liegenden, während die übrigen verdeckt sind. Liste diese Werte von der Ebene der Wurzel bis zur tiefsten Ebene auf.

Funktion

rightSideView(root: integer-array) → integer-array

rootinteger-array: der Baum in Heap-Reihenfolge, mit -1 für eine leere Stelle
Gibt zurückinteger-array: Der jeweils ganz rechte Wert jeder Ebene, beginnend mit der obersten Ebene

Einschränkungen

1 ≤ root.length ≤ 32767
Jedes root[i] ist -1 oder ein Wert mit 0 ≤ root[i] ≤ 10⁴.
Die Werte der Knoten sind eindeutig.
root[0] ist niemals -1, daher hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten noch zusätzliche -1-Einträge enthalten.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und der Baum hat höchstens 14 Ebenen.

Beispiele

Eingabe: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Ausgabe: [5, 9, 1, 3]
Erklärung: Von rechts siehst du 5, 9 und 1 (Index 6). Die vierte Ebene enthält nur 3 an Index 8 unter 7 im linken Teilbaum. Auf der rechten Seite reicht nichts so tief, daher ist 3 sichtbar.

Eingabe: root = [6, 0, -1, 8, -1, -1, -1]
Ausgabe: [6, 0, 8]
Erklärung: Der Baum ist eine Kette aus linken Kindern: 6, 0, 8. Jede Ebene enthält einen Knoten, daher siehst du alle drei, obwohl keiner von ihnen ein rechtes Kind ist.

Eingabe: root = [42]
Ausgabe: [42]
Erklärung: Ein Array der Länge 1: Der Wurzelknoten 42 hat überhaupt keine Kindplätze, und die Ansicht besteht aus diesem einen Wert.

Weiterführende Frage

Wie würdest du die rechte Seitenansicht eines Baums erhalten, in dem jeder Knoten beliebig viele Kinder haben kann, die als Liste von links nach rechts gespeichert sind?

Tipps

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

0 von 3 geöffnet

Lösung

Du siehst den ganz rechten Knoten jeder Ebene, und er muss kein rechter Kindknoten sein: Der letzte Wert von Beispiel 1 befindet sich im linken Teilbaum. Bei einer Breitensuche ist dieser Knoten der letzte in jeder Runde; bei einer Tiefensuche, die zuerst nach rechts geht, wird er vor jedem anderen Knoten auf seiner Ebene erreicht.

Breitensuche, letzter Knoten jeder Ebene

Idee

Verarbeite den Baum Runde für Runde auf jeweils einer Ebene. Zu Beginn einer Runde enthält die Warteschlange genau eine Ebene von links nach rechts. Daher ist der letzte Index, den du in dieser Runde aus der Warteschlange nimmst, der am weitesten rechts liegende Knoten dieser Ebene, und sein Wert kommt in die Antwort.

In Beispiel 1 lauten die Runden [5], [2, 9], [7, 4, 1] und [3], und ihre letzten Einträge ergeben 5, 9, 1, 3. Entscheidend ist die Ebene, nicht die Seite: 3 befindet sich im linken Teilbaum, ist aber allein auf seiner Ebene.

Jeder Index wird einmal in die Warteschlange eingefügt und einmal daraus entfernt, daher beträgt die Laufzeit O(n). Die Warteschlange wächst bis zur breitesten Ebene, im schlimmsten Fall auf O(n).

Algorithmus

Füge den Index der Wurzel 0 zur Warteschlange hinzu.
Beginne eine Runde, indem du die Länge der Warteschlange s speicherst.
Entnimm s Indizes aus der Warteschlange. Füge für jeden Index i 2i+1 und danach 2i+2 zur Warteschlange hinzu, falls sie kleiner als die Länge des Arrays sind und nicht -1.
Füge den Wert des letzten in der Runde entnommenen Index hinzu.
Wiederhole den Vorgang, bis die Warteschlange leer ist, und gib dann die Antwort zurück.

from collections import deque


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

Tiefensuche, zuerst der rechte Nachfolger

Idee

Durchlaufe den Baum tiefensuchend, wobei du zuerst das rechte und dann das linke Kind besuchst, und führe die Tiefe mit, wobei sie an der Wurzel 0 beträgt. Beim ersten Erreichen der Tiefe d enthält die Antwort genau d Werte. Füge dann den Wert des Knotens hinzu und ignoriere jeden späteren Knoten auf dieser Ebene.

Dieser erste Knoten ist der am weitesten rechts liegende: Wo sich zwei Pfade zu einer Ebene trennen, folgt der Durchlauf dem rechten Zweig bis nach unten, bevor er zurückgeht und den linken Zweig besucht. In Beispiel 1 besucht der Durchlauf 5, 9, 1, 2, 4, 7, 3: Er überspringt 2, 4 und 7, deren Tiefen bereits einen Wert haben, und fügt 3 hinzu.

Jeder Knoten wird einmal besucht, Laufzeit O(n), mit einem Aufruf pro Ebene auf dem Stack, höchstens 14.

Algorithmus

Beginne mit einer leeren Antwort und der Wurzel auf Tiefe 0.
Überspringe einen Index, der außerhalb des Arrays liegt oder den Wert -1 enthält.
Wenn die Länge der Antwort der Tiefe entspricht, füge den Wert hinzu: Der Durchlauf hat eine neue Ebene erreicht, und zwar von rechts.
Durchlaufe zuerst rekursiv das rechte Kind 2i+2, dann das linke Kind 2i+1, jeweils eine Ebene tiefer.
Gib die Antwort zurück.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Stolperfallen und Grenzfälle

Nur den rechten Kindern von der Wurzel aus folgen. Beispiel 1 ergibt dann [5, 9, 1] und lässt 3 aus; Beispiel 2 ergibt [6].
Den letzten Eintrag jeder Ebene auslesen, root[2^(d+1)-2]. In Beispiel 2 enthält Index 6 den Wert -1; der sichtbare Knoten ist 8 an Index 3.
Die Längenprüfung für eine Kindposition überspringen. In Beispiel 1 ist 3 der letzte Eintrag, daher sind seine Kindpositionen 17 und 18 nicht vorhanden.
Zuerst das rechte Kind in die Warteschlange aufnehmen und dabei den letzten Knoten jeder Runde behalten. So erhält man die linke Ansicht, [5, 2, 7, 3].
Beim Durchlaufen zuerst nach rechts spätere Knoten frühere überschreiben lassen, wodurch ebenfalls die linke Ansicht entsteht.

Häufige Fragen3

Wie hoch sind die Zeit- und Speicherkomplexität der rechten Seitenansicht eines Binärbaums?

Die Laufzeit beträgt O(n) für n Knoten, und keine Lösung kann Knoten überspringen, da der rechteste Knoten einer Ebene an beliebiger Stelle hängen kann. Der Speicherbedarf beträgt O(w) für die Warteschlange, wobei w die breiteste Ebene ist, oder O(h) für die Suche zuerst nach rechts in einem Baum mit h Ebenen.

Kann eine Tiefensuche mit Links zuerst das Problem lösen?

Ja, wenn du den ersten Wert überschreibst, statt ihn beizubehalten. Bei einem Durchlauf von links nach rechts werden die Knoten jeder Ebene von links nach rechts erreicht. Speichere daher den Wert jedes Knotens in seiner Tiefe und lass spätere Knoten frühere Werte ersetzen. Auf jeder Ebene bleibt so der Wert des rechtesten Knotens übrig. Das ist weiterhin O(n), schreibt aber einmal pro Knoten.

Sollte ich hier eine Breitensuche oder eine Tiefensuche verwenden?

Beide sind linear. Die Breitensuche folgt der Definition: eine Ebene pro Runde. Die Tiefensuche behält nur den aktuellen Pfad bei, wodurch sie bei einem breiten Baum Speicher spart; ihre rekursive Form ist um einige Zeilen kürzer.

def rightSideView(root):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Erwartete Ausgabe

[5, 9, 1, 3]