Vertical Order Traversal of a Binary Tree

+10

Ein Binärbaum wird im Heap-Format im Array root gespeichert: Die Wurzel befindet sich am Index 0, die Kinder des Index i befinden sich bei 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet eine leere Stelle, und das Array kann mit zusätzlichen -1-Einträgen enden.

Die Wurzel befindet sich in Spalte 0; ein linkes Kind befindet sich eine Spalte links von seinem Elternknoten, ein rechtes Kind eine Spalte rechts. Gib für jede Spalte eine Liste zurück, von links nach rechts. Liste die Knoten innerhalb einer Spalte von oben nach unten auf und ordne Knoten, die sich eine Spalte und eine Tiefe teilen, nach aufsteigendem Wert.

Funktion

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: der Baum in Heap-Reihenfolge, mit -1 für eine leere Stelle
Gibt zurückinteger-2d-array: eine Liste von Werten pro Spalte, beginnend mit der Spalte ganz links, jeweils von oben nach unten

Einschränkungen

1 ≤ root.length ≤ 32767
Jedes root[i] ist -1 oder ein Wert mit 0 ≤ root[i] ≤ 5000, 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, 1, 7], [9], [6]]
Erklärung: Spalte 0 enthält die Wurzel 5, darunter zwei Ebenen tiefer 7 und 1. Diese beiden haben dieselbe Spalte und Tiefe, daher kommt 1 vor 7, obwohl 7 weiter links steht.

Eingabe: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Ausgabe: [[2, 5], [1, 4], [3]]
Erklärung: Spalte -1 enthält 2 in Tiefe 1 und 5 in Tiefe 3 (das linke Kind von 4). Spalte 0 enthält die Wurzel 1 und 4 an Index 4. Spalte 1 enthält nur 3.

Eingabe: root = [6, -1, -1]
Ausgabe: [[6]]
Erklärung: 6 hat keine Nachfolger, daher besteht die Antwort aus einer einzelnen Spalte, [6].

Weiterführende Frage

Jeder Wert ist höchstens 5000. Kannst du das nutzen, um die Vergleichssortierung wegzulassen und die Aufgabe in O(n + 5000) Zeit abzuschließen?

Lösung

Jeder Knoten hat drei Schlüssel: Spalte, Tiefe und Wert. Die Antwort besteht aus den nach diesen Schlüsseln geordneten Knoten, jeweils eine Liste pro Spalte. Bei gleichen Spalten und Tiefen entscheidet der Wert, nicht die Reihenfolge von links nach rechts, in der die Traversierung auf die Knoten trifft. Deshalb musst du sortieren: entweder alle Knoten auf einmal oder jede Ebene einer Breitensuche.

Erfasse jeden Knoten und sortiere ihn anschließend

Idee

Besuche jeden Knoten genau einmal, in beliebiger Reihenfolge, und notiere das Tripel (Spalte, Tiefe, Wert). Ein Schritt zu einem Kind erhöht die Tiefe um 1 und verschiebt die Spalte um 1 nach links oder rechts. Sortiere dann die Tripel nach Spalte, Tiefe und Wert. Die Knoten jeder Spalte stehen nun zusammen und in der erforderlichen Reihenfolge. Gehe die sortierte Liste durch und beginne eine neue innere Liste, sobald sich die Spalte ändert.

In Beispiel 1 werden die Tripel von Spalte 0 sortiert zu (0, 0, 5), (0, 2, 1), (0, 2, 7). Die Sortierung mit O(n log n) bestimmt den Aufwand gegenüber dem Durchlauf mit O(n), und die Tripel benötigen O(n) Speicherplatz.

Algorithmus

Lege (Index 0, Spalte 0, Tiefe 0) auf einen Stack.
Nimm einen Knoten vom Stack, speichere (Spalte, Tiefe, Wert) und lege jedes tatsächliche Kind mit Spalte col-1 oder col+1 und Tiefe depth+1 auf den Stack.
Wenn der Stack leer ist, sortiere die Tripel nach Spalte, dann Tiefe, dann Wert.
Gehe sie durch und beginne jeweils eine neue Liste, wenn sich die Spalte ändert.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Ebene für Ebene sortieren, innerhalb jeder Ebene

Idee

Eine Breitensuche verarbeitet jeweils eine Ebene. Wenn jeder Knoten beim Verarbeiten seinen Wert an die Liste seiner Spalte anhängt, ist jede Liste bereits von oben nach unten sortiert, sodass die Tiefe nicht sortiert werden muss. Gleichstände treten nur innerhalb einer Ebene auf. Sortiere daher jede Ebene nach Spalte und anschließend nach Wert, bevor du sie verarbeitest.

In Beispiel 1 kommt Ebene 2 in den Spalten -2, 0, 0, 2 als 4, 7, 1, 6 an und wird zu 4, 1, 7, 6 sortiert, sodass Spalte 0 zu [5, 1, 7] wird. Die belegten Spalten bilden einen lückenlosen Bereich, daher genügt es, die kleinste und die größte Spalte zu verfolgen.

Das Sortieren einer Ebene mit m Knoten kostet O(m log m). Der Aufwand im schlimmsten Fall bleibt O(n log n), da die letzte Ebene eines vollständigen Baums etwa die Hälfte der Knoten enthält. Der Speicherbedarf beträgt O(n).

Algorithmus

Beginne mit einer Ebene, die (Index 0, Spalte 0) enthält.
Sortiere die Ebene nach Spalte und dann nach Wert.
Füge in dieser Reihenfolge jeden Wert zur Liste seiner Spalte hinzu und sammle seine echten Kinder mit den Spalten col-1 und col+1 in der nächsten Ebene.
Wiederhole den Vorgang, bis eine Ebene leer ist, und verfolge dabei die kleinste und die größte Spalte.
Gib die Listen von der kleinsten bis zur größten Spalte zurück.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Stolperfallen und Grenzfälle

Bei Gleichständen die Reihenfolge von links nach rechts beibehalten. Eine Breitensuche ohne Sortierung pro Ebene liefert für Spalte 0 von Beispiel 1 [5, 7, 1] statt [5, 1, 7].
Werte bei einem Tiefendurchlauf ohne Sortierung anhängen. In [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5] hängt ein Durchlauf zuerst nach links die 5 (Tiefe 3) vor der 3 (Tiefe 1) an Spalte 1 an.
Nach Spalte und Wert, aber nicht nach Tiefe sortieren. Spalte 0 von Beispiel 1 ergibt dann [1, 5, 7].
Die Spalten mit Zeichenfolgen als Schlüssel versehen. Bei lexikografischer Sortierung steht "-1" vor "-2", sodass die Spalten links von 0 in der falschen Reihenfolge erscheinen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der vertikalen Traversierung eines Binärbaums?

Das Sortieren aller Knoten nach Spalte, Tiefe und Wert kostet O(n log n) und dominiert den O(n)-Durchlauf. Das Sortieren Ebene für Ebene hat denselben Worst Case, da die letzte Ebene eines vollständigen Baums etwa die Hälfte der Knoten enthält. Der Speicherbedarf beträgt O(n).

Kann die vertikale Traversierung nach Ebenen ohne Sortierung erfolgen?

Nur wenn Gleichstände von links nach rechts geordnet sind. Dann liefert eine Breitensuche, die jeden Wert an die Liste seiner Spalte anhängt, die Antwort in O(n). Bei nach Werten geordneten Gleichständen benötigst du eine gewisse Sortierung, aber nur innerhalb einer Ebene, da nur Knoten auf derselben Ebene gleichauf sein können.

Wie hängt die vertikale Traversierung mit der Ansicht von oben und der Ansicht von unten zusammen?

Alle drei gruppieren die Knoten nach denselben Spaltennummern. Die Draufsicht behält in jeder Spalte den obersten Knoten und die Unteransicht den untersten. Die Traversierung in vertikaler Reihenfolge berücksichtigt jeden Knoten und ordnet sie, wenn sich mehrere auf derselben Ebene befinden, nach ihrem Wert, während die Ansichten anhand der Position auswählen.

def verticalTraversal(root):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

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