Bottom View of Binary Tree

Q: Wie hoch ist die Zeitkomplexität der unteren Ansicht eines binären Baums?

O(n) für n Knoten: Die Breitensuche bearbeitet jeden Knoten einmal und führt dabei einen Schreibvorgang in einer Hash-Map aus. Eine geordnete Map wie eine Tree-Map fügt für w Spalten einen Faktor von log w hinzu.

MittelBaumdurchlauf Hashing

+10

Das Array root enthält einen Binärbaum: die Wurzel an Index 0, die Kinder von Index i an 2i+1 (links) und 2i+2 (rechts), -1 für eine leere Stelle und möglicherweise zusätzliche -1-Einträge am Ende.

Die Wurzel befindet sich in Spalte 0; ein Schritt nach links verschiebt dich um eine Spalte nach links, ein Schritt nach rechts um eine Spalte nach rechts. Von unten betrachtet zeigt jede Spalte ihren tiefsten Knoten, und bei Gleichstand den letzten auf dieser Ebene, wenn man von links nach rechts liest (den mit dem größeren Index). Gib die Werte zurück, die du siehst, beginnend mit der Spalte ganz links.

Funktion

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

rootinteger-array: der Baum in Heap-Reihenfolge, mit -1 für eine leere Position
Gibt zurückinteger-array: der von unten betrachtete Wert in jeder Spalte, beginnend mit der Spalte ganz links

Einschränkungen

1 ≤ root.length ≤ 32767
Jedes root[i] ist -1 oder ein Wert mit 0 ≤ root[i] ≤ 10⁴, und kein Wert kommt zweimal vor.
root[0] ist niemals -1, daher 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 = [5, 2, 9, 4, 7, 1, 6]
Ausgabe: [4, 2, 1, 9, 6]
Erklärung: Spalte 0 enthält 5 und zwei Ebenen darunter 7 (Index 4) und 1 (Index 5). 1 kommt auf derselben Ebene später, also wird es angezeigt. Die Spalten -2, -1, 1 und 2 enthalten 4, 2, 9 und 6.

Eingabe: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Ausgabe: [5, 4, 3]
Erklärung: Spalte -1 enthält 2 und zwei Ebenen tiefer 5 (Index 9), daher siehst du 5. In Spalte 0 befindet sich 4 unterhalb der Wurzel. Spalte 1 enthält nur 3.

Eingabe: root = [8, -1, -1, -1]
Ausgabe: [8]
Erklärung: Jede Position nach der Wurzel ist -1, also ist 8 der einzige Knoten und Spalte 0 die einzige Spalte.

Weiterführende Frage

Wenn bei einem Gleichstand auf der tiefsten Ebene einer Spalte alle gleichrangigen Knoten von links nach rechts zurückgegeben werden sollen, wie würde sich die Breitensuche-Version ändern? Was würde Spalte 0 von Beispiel 1 ergeben?

Lösung

Jede Spalte zeigt ihren tiefsten Knoten, und bei Gleichstand wird der Knoten ausgewählt, der in der Ebenenreihenfolge später kommt. Eine Breitensuche besucht die Knoten in Ebenenreihenfolge, daher ist der zuletzt besuchte Knoten einer Spalte die Antwort: Lass jeden Knoten den Eintrag seiner Spalte überschreiben.

Tiefensuche, tiefster Knoten pro Spalte

Idee

Durchlaufe den Baum tiefensuchend, gib jedem Knoten seine Spalte und Tiefe mit und speichere für jede Spalte die Tiefe und den Wert des bisher tiefsten Knotens.

Wenn du den linken Teilbaum vor dem rechten besuchst, triffst du die Knoten einer Ebene von links nach rechts an. Der gesuchte Knoten ist also der zuletzt angetroffene: Ersetze den bisherigen Wert, wenn die Tiefe größer oder gleich ist. In Beispiel 1 trifft der Durchlauf auf 7 und dann auf 1, beide mit Tiefe 2 in Spalte 0, und 1 belegt die Spalte.

Die Spalten bilden einen zusammenhängenden Bereich. Verfolge daher die kleinste und die größte Spalte und lies jede Spalte dazwischen aus. Ein Besuch pro Knoten ergibt eine Laufzeit von O(n), und die Rekursion ist bei einem Baum mit h Ebenen h Aufrufe tief.

Algorithmus

Besuche die Wurzel mit Spalte 0 und Tiefe 0.
Überspringe den Index i, wenn er hinter dem Ende des Arrays liegt oder root[i] -1 ist.
Wenn die Spalte noch keinen Knoten enthält oder diese Tiefe größer oder gleich der gespeicherten ist, speichere diese Tiefe und diesen Wert.
Besuche 2i+1 mit Spalte col-1, dann 2i+2 mit Spalte col+1, jeweils eine Ebene tiefer.
Gib die gespeicherten Werte zurück, beginnend mit der kleinsten Spalte.

def bottomView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the deepest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later in level order.
        if col not in best or depth >= best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Breitensuche, letzter Knoten pro Spalte

Idee

Eine Warteschlange, in die jeder Knoten beim Verlassen zuerst sein linkes und dann sein rechtes Kind einfügt, gibt die Knoten in Ebenenreihenfolge aus: jeder Knoten der Tiefe d vor jedem Knoten der Tiefe d+1 und jede Ebene von links nach rechts. Unter den Knoten einer Spalte kommt der tiefste zuletzt heraus, und bei gleicher Tiefe der weiter rechts liegende. Wenn also jeder Knoten den Platz seiner Spalte überschreibt, enthält am Ende jeder Platz den von unten gesehenen Knoten, ohne dass die Tiefe verglichen werden muss.

In Beispiel 1 schreibt 7 in Spalte 0 und 1 überschreibt diesen Eintrag.

Jeder Knoten erfordert einen Warteschlangenbesuch und einen Schreibvorgang in die Map: O(n) Zeit. Die Warteschlange kann eine ganze Ebene enthalten, also etwa die Hälfte der Knoten; daher beträgt der Speicherbedarf O(n).

Algorithmus

Füge das Paar (Index 0, Spalte 0) in eine Warteschlange ein.
Nimm ein Paar (i, col) heraus und speichere root[i] unter col, wobei ein früherer Wert ersetzt wird.
Füge (2i+1, col-1) und dann (2i+2, col+1) für jedes Kind hinzu, das sich innerhalb des Arrays befindet und nicht -1 ist.
Wiederhole den Vorgang, bis die Warteschlange leer ist, und verfolge dabei die kleinste und die größte Spalte.
Gib die Werte der Map zurück, beginnend mit der kleinsten Spalte.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Stolperfallen und Grenzfälle

Nur bei einer strikt größeren Tiefe in der Tiefensuche ersetzen. Beispiel 1 behält dann 7 statt 1.
Bei der Breitensuche den ersten Knoten jeder Spalte beibehalten. Das ist die Draufsicht.
Das rechte Kind vor dem linken in die Warteschlange einfügen. Jede Ebene kommt dann von rechts nach links heraus, und bei Gleichständen wird der falsche Knoten gewählt.
Die Blätter als Antwort nehmen. In Beispiel 1 wird das Blatt 7 von 1 verdeckt, und in Beispiel 2 hat der Knoten 4 ein Kind und liegt dennoch ganz unten in Spalte 0.
Die Spalten als Text sortieren. Als Zeichenfolgen landet "-10" zwischen "-1" und "-2".

Häufige Fragen3

Was ist die Unteransicht eines Binärbaums?

Gib der Wurzel die Spalte 0, jedem Schritt nach links eine Spalte weniger und jedem Schritt nach rechts eine mehr. Die Ansicht von unten listet den tiefsten Knoten jeder Spalte von links nach rechts auf. Bei einem Gleichstand in der Tiefe entscheidet dieses Problem nach Ebenenreihenfolge und behält den späteren Knoten bei.

Wie hoch ist die Zeitkomplexität der unteren Ansicht eines binären Baums?

O(n) für n Knoten: Die Breitensuche bearbeitet jeden Knoten einmal und führt dabei einen Schreibvorgang in einer Hash-Map aus. Eine geordnete Map wie eine Tree-Map fügt für w Spalten einen Faktor von log w hinzu.

Was ist der Unterschied zwischen der Draufsicht und der Unteransicht?

Beide wählen einen Knoten pro Spalte aus. Die Draufsicht wählt den obersten Knoten und die Unteransicht den untersten. In der Breitensuche-Variante behält die Draufsicht den ersten Wert, den eine Spalte erhält; die Unteransicht überschreibt ihn jedes Mal.

def bottomView(root):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 4, 7, 1, 6]

Erwartete Ausgabe

[4, 2, 1, 9, 6]