Top View of Binary Tree

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

Eine Breitensuche besucht jeden der n Knoten einmal mit einem O(1) -Nachschlagen in der Map pro Knoten. Wenn du die kleinste und größte Spalte erfasst, läuft sie daher in O(n) Zeit. Eine nach Spalten geordnete Map benötigt bei w Spalten O(n log w) .

MittelBaumdurchlauf Hashing

+10

Du erhältst einen Binärbaum, der in der Array-Variable root in Heap-Reihenfolge gespeichert ist: die Wurzel an Index 0, die Kinder von Index i an 2*i+1 (links) und 2*i+2 (rechts) und -1 für eine leere Stelle.

Die Wurzel befindet sich in Spalte 0; ein linkes Kind steht eine Spalte links von seinem Elternknoten und ein rechtes Kind eine Spalte rechts. Von oben gesehen siehst du den Knoten mit der geringsten Tiefe in jeder Spalte; bei Gleichstand denjenigen, der in seiner Ebene von links nach rechts zuerst kommt (mit dem kleineren Index). Gib die Werte zurück, die du siehst, von der am weitesten links gelegenen Spalte bis zur am weitesten rechts gelegenen.

Funktion

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

rootinteger-array: der Baum in Heap-Reihenfolge, mit -1 für eine leere Stelle
Gibt zurückinteger-array: der von oben aus betrachtete Wert in jeder Spalte, beginnend mit der ganz linken Spalte

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, 5, 9, 6]
Erklärung: Von links nach rechts enthalten die Spalten 4 (Spalte -2), 2 (-1), die Wurzel 5 (0), 9 (1) und 6 (2). 7 und 1 befinden sich ebenfalls in Spalte 0, aber die Wurzel liegt über ihnen.

Eingabe: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Ausgabe: [2, 1, 4]
Erklärung: 2 befindet sich in Spalte -1. Sein rechtes Kind 3 bei Index 4 ist wieder in Spalte 0 unter der Wurzel und daher verborgen. 4 bei Index 10, das rechte Kind von 3, ist allein in Spalte 1.

Eingabe: root = [6, -1, -1]
Ausgabe: [6]
Erklärung: Die Indizes 1 und 2 enthalten -1, daher steht 6 allein in Spalte 0 und bildet die gesamte Ansicht.

Weiterführende Frage

Bei Knotenobjekten statt einem Array gibt es keinen Index, der einen Gleichstand entscheiden könnte. Wie würdest du die Gleichstandsregel formulieren, und ändert sich dein Code für die Breitensuche?

Lösung

Jede Spalte zeigt ihren flachsten Knoten und bei Gleichstand denjenigen, der in der Ebenenreihenfolge zuerst kommt. Das ist genau die Reihenfolge, in der eine Breitensuche die Knoten besucht, daher ist der erste Knoten, auf den die Suche in einer Spalte trifft, die Antwort. Eine Tiefensuche funktioniert ebenfalls, aber dabei müssen die Tiefen erfasst und Gleichstände sorgfältig aufgelöst werden.

Tiefensuche, oberflächlichster Knoten pro Spalte

Idee

Durchlaufe den Baum tiefensuchend mit der Spalte und Tiefe jedes Knotens und speichere für jede Spalte die Tiefe und den Wert des bisher gefundenen Knotens mit der geringsten Tiefe.

Ersetze den Wert nur bei einer strikt geringeren Tiefe. Von zwei Knoten mit gleicher Tiefe wird derjenige, der in der Ebenenreihenfolge zuerst kommt, bei einer Durchsuchung zuerst erreicht, die jeden linken Teilbaum vor dem zugehörigen rechten Teilbaum erkundet, denn an der Stelle, an der sich die beiden Pfade trennen, geht sie nach links. Wird auch bei gleicher Tiefe ersetzt, gewinnt der spätere Knoten: Ist der Index 3 leer und befinden sich Knoten an den Indizes 19 und 23, liegen beide in Spalte -2 auf Tiefe 4, und die Antwort ist der Knoten an Index 19.

Die belegten Spalten bilden einen zusammenhängenden Bereich, da ein Knoten in Spalte -3 Vorfahren in den Spalten -1 und -2 hat; verfolge daher die kleinste und die größte Spalte. Jeder Knoten wird einmal besucht; die Laufzeit beträgt O(n), und die Rekursion ist etwa h Aufrufe tief.

Algorithmus

Besuche die Wurzel mit Spalte 0 und Tiefe 0. Kehre sofort zurück, wenn ein Index außerhalb des Arrays liegt oder den Wert -1 enthält.
Wenn die Spalte noch keinen Knoten hat oder diese Tiefe strikt kleiner als die gespeicherte ist, speichere diese Tiefe und den Wert.
Besuche 2i+1 mit Spalte col-1, dann 2i+2 mit Spalte col+1, eine Ebene tiefer.
Gib die gespeicherten Werte von der kleinsten bis zur größten Spalte zurück.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first 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, erster Knoten pro Spalte

Idee

Eine Warteschlange, die zuerst die Wurzel, dann den linken und anschließend den rechten Nachfolger jedes Knotens verarbeitet, gibt die Knoten in Ebenenreihenfolge aus: jeden Knoten der Tiefe d vor jedem Knoten der Tiefe d+1 und jede Ebene von links nach rechts. Das entspricht der Priorität des Problems: Der erste Knoten, den eine Spalte erhält, ist der von oben sichtbare, und jeder spätere wird übersprungen.

Jeder Knoten erfordert einen Map-Zugriff, insgesamt also O(n). Die Warteschlange kann eine ganze Ebene enthalten, also bis zu etwa der Hälfte aller Knoten; der Speicherbedarf beträgt daher O(n).

Algorithmus

Füge das Paar (Index 0, Spalte 0) in eine Warteschlange ein.
Nimm ein Paar (i, col) heraus. Wenn die Map keinen Eintrag für col enthält, speichere dort root[i].
Füge für jedes vorhandene Kind (2i+1, col-1) und anschließend (2i+2, col+1) hinzu.
Wenn die Warteschlange leer ist, gib die Werte der Map von der kleinsten bis zur größten Spalte zurück.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first 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 shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[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 [top[col] for col in range(min(top), max(top) + 1)]

Stolperfallen und Grenzfälle

Den ersten Knoten beibehalten, den eine Tiefensuche findet. Wenn das linke Kind der Wurzel ein rechtes Kind mit einem rechten Kind hat (Spalte 1, Tiefe 3), trifft die Suche darauf, bevor sie das rechte Kind der Wurzel erreicht (Spalte 1, Tiefe 1).
Zuerst das rechte Kind in die Warteschlange einreihen: Bei Gleichständen wird der falsche Knoten ausgewählt.
Die Spalten als Text sortieren: "-1" wird vor "-2" sortiert.
Annehmen, dass der linke Teilbaum die negativen Spalten belegt. In Beispiel 2 befindet sich der Knoten 4 im linken Teilbaum der Wurzel und in Spalte 1.

Häufige Fragen3

Was ist die Draufsicht eines Binärbaums?

Nummeriere die Spalten ausgehend von der Wurzel mit 0, für ein linkes Kind jeweils eine Spalte nach links und für ein rechtes Kind eine Spalte nach rechts. Die Draufsicht listet für jede Spalte von links nach rechts den Knoten auf, der der Wurzel am nächsten ist.

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

Eine Breitensuche besucht jeden der n Knoten einmal mit einem O(1)-Nachschlagen in der Map pro Knoten. Wenn du die kleinste und größte Spalte erfasst, läuft sie daher in O(n) Zeit. Eine nach Spalten geordnete Map benötigt bei w Spalten O(n log w).

Worin unterscheidet sich die Draufsicht von der linken Ansicht und der Unteransicht?

Die linke Ansicht wählt den ersten Knoten jeder Ebene aus. Die Draufsicht wählt den obersten Knoten jeder Spalte aus. Die Unteransicht wählt den untersten Knoten pro Spalte aus, daher überschreibt eine Breitensuche dafür jede Spalte, statt den ersten Knoten beizubehalten.

def topView(root):
    # Schreibe hier deinen Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

[4, 2, 5, 9, 6]