Left View of Binary Tree

+10

Du erhältst einen Binärbaum als Array root in Heap-Reihenfolge: Die Wurzel steht am Index 0, die Kinder des Index i stehen bei 2*i+1 (links) und 2*i+2 (rechts), und -1 kennzeichnet eine leere Stelle. Das Array kann mit zusätzlichen -1-Einträgen enden.

Stell dich links neben den Baum. Auf jeder Ebene siehst du einen Knoten, den ganz linken; der Rest der Ebene verbirgt sich dahinter. Gib die Werte zurück, die du siehst, von der obersten Ebene nach unten.

Funktion

leftView(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 linkeste 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 Knotenwerte sind verschieden.
root[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.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und der Baum hat höchstens 14 Ebenen.

Beispiele

Eingabe: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Ausgabe: [3, 8, 6, 1]
Erklärung: 8 ist ein Blatt, daher enthalten die dritte und vierte Ebene nur 6 (Index 6) und 1 (Index 13), beide unter dem rechten Kind 5. Du siehst sie trotzdem: [3, 8, 6, 1].

Eingabe: root = [10, -1, -1]
Ausgabe: [10]
Erklärung: Die Indizes 1 und 2 enthalten -1, daher hat 10 keine Kinder und die Ansicht besteht nur aus der Wurzel.

Eingabe: root = [1, 2, 3, 4, 5, 6, 7]
Ausgabe: [1, 2, 4]
Erklärung: Ein vollständiger Baum mit drei Ebenen. Die ganz linken Positionen der Ebenen haben die Indizes 0, 1 und 3 und enthalten 1, 2 und 4.

Weiterführende Frage

Ebene d belegt die Indizes 2^d-1 bis 2^(d+1)-2. Kannst du die Ansicht erstellen, indem du diese Bereiche durchläufst, ohne Warteschlange oder Rekursion? Wie aufwendig ist das bei einem aufgefüllten Array?

Lösung

Dem Wurzelknoten über die linken Kindknoten zu folgen, schlägt fehl, wenn der linke Teilbaum kürzer ist: Im ersten Beispiel werden die unteren Ebenen über den rechten Teilbaum erreicht. Du möchtest den ersten Knoten jeder Ebene. Die Breitensuche liefert dir jede Ebene von links nach rechts; bei einer Tiefensuche, die zuerst nach links geht, triffst du auf jeder Ebene zuerst auf den am weitesten links stehenden Knoten.

Breitensuche, erster Knoten jeder Ebene

Idee

Eine rundenweise verarbeitete Warteschlange liefert dir die Ebenen nacheinander. Zu Beginn einer Runde enthält die Warteschlange genau eine Ebene von links nach rechts, denn jedes während der Runde hinzugefügte Kind wird dahinter eingereiht. Nimm so viele Indizes heraus, queue die Kinder jedes Indexes, beginnend mit dem linken, ein und behalte den ersten Wert.

Im ersten Beispiel lauten die Runden [3], [8, 5], [6] und [1]; sie behalten 3, 8, 6 und 1. Die 8 fügt nichts hinzu, weil ihre Kindpositionen 3 und 4 den Wert -1 enthalten.

Jeder Knoten wird einmal in die Warteschlange eingereiht und wieder daraus entfernt: Laufzeit O(n). Die Warteschlange enthält eine ganze Ebene, bei einem vollständigen Baum mit 14 Ebenen bis zu 8192 Indizes.

Algorithmus

Starte eine Warteschlange mit dem Index 0 und einer leeren Antwort.
Solange die Warteschlange nicht leer ist, sei s ihre Größe und entferne s Indizes. Hänge den Wert des ersten an.
Füge für jeden entfernten Index i 2i+1 und dann 2i+2 zur Warteschlange hinzu. Überspringe Indizes außerhalb des Endes und Einträge mit dem Wert -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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 das linke Kind

Idee

Durchlaufe den Baum tiefensuchend, zuerst den linken und dann den rechten Teilbaum, und übergib die Tiefe jedes Knotens. Der erste Knoten, den der Durchlauf in Tiefe d erreicht, ist der am weitesten links liegende auf Ebene d. Nimm den am weitesten links liegenden Knoten x einer Ebene und einen beliebigen Knoten y rechts von ihm: Am letzten gemeinsamen Knoten ihrer Pfade führt der Pfad zu x nach links und der zu y nach rechts, und der Durchlauf beendet den linken Zweig, bevor er nach rechts abbiegt.

Der Durchlauf steigt jeweils eine Ebene hinab. Wenn er also erstmals Tiefe d erreicht, enthält das Ergebnis genau d Werte. Speichere einen Knoten, wenn d der Länge des Ergebnisses entspricht; eine Menge bereits besuchter Tiefen ist nicht nötig.

Jeder Knoten wird einmal besucht: Laufzeit O(n). Der Speicherbedarf entspricht einem Aufruf pro Ebene, hier höchstens 14. Die R-Version verwaltet ihren eigenen Stack und fügt den rechten Knoten vor dem linken hinzu.

Algorithmus

Erstelle eine leere Antwort und rufe visit(0, 0) auf.
Gib in visit(i, d) sofort zurück, wenn i außerhalb des Arrays liegt oder root[i] -1 ist.
Wenn d der Länge der Antwort entspricht, hat der Durchlauf die Ebene d zum ersten Mal erreicht: Füge root[i] hinzu.
Rufe visit(2i+1, d+1) auf, dann visit(2i+2, d+1).
Gib die Antwort zurück, sobald der erste Aufruf abgeschlossen ist.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Stolperfallen und Grenzfälle

Nur den linken Kindern von der Wurzel aus folgen. Im ersten Beispiel endet das bei 8, wodurch 6 und 1 übersehen werden.
Den ersten Eintrag jeder Ebene lesen, root[2^d-1]. Im ersten Beispiel enthält der erste Eintrag der dritten Ebene, Index 3, -1, während ihr einziger Knoten an Index 6 steht.
Beim Tiefendurchlauf zuerst das rechte Kind besuchen. Der erste auf jeder Ebene angetroffene Knoten ist dann der rechteste.
Ein Kind ohne Prüfung der Grenzen lesen. Die 1 an Index 13 hat Kindpositionen 27 und 28, die außerhalb des 14 Einträge umfassenden Arrays liegen.

Häufige Fragen3

Ist die linke Ansicht dasselbe wie die linke Grenze eines Baums?

Nein. Die linke Begrenzung ist ein Pfad: Er beginnt beim linken Kind der Wurzel, geht nach links, wenn das möglich ist, andernfalls nach rechts, und endet vor einem Blatt. Die linke Ansicht nimmt einen Knoten pro Ebene aus einem beliebigen Zweig. Im ersten Beispiel ist die Begrenzung leer, da 8 ein Blatt ist, aber die Ansicht zeigt 8, 6 und 1.

Wie hoch sind Zeit- und Speicherkomplexität der linken Ansicht?

Beide Lösungen betrachten jeden Knoten genau einmal, daher beträgt die Laufzeit O(n). Die Breitensuche-Warteschlange enthält eine ganze Ebene, etwa die Hälfte der Knoten eines vollständigen Baums. Der Linkszuerst-Durchlauf hält einen Aufruf pro Ebene, O(h) für h Ebenen.

Wie änderst du die Lösung, um die richtige Ansicht zu erhalten?

In der Breitensuche behältst du den letzten Wert jeder Runde statt des ersten. In der Tiefensuche besuchst du zuerst das rechte Kind; dann ist der erste Knoten, den der Durchlauf auf jeder Ebene erreicht, der am weitesten rechts liegende.

def leftView(root):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Erwartete Ausgabe

[3, 8, 6, 1]