Binary Tree Zigzag Level Order Traversal
Du erhältst einen Binärbaum, der im Array root gespeichert ist. 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 Position, und das Array kann mit zusätzlichen -1-Einträgen enden.
Gib die Knotenwerte Ebene für Ebene in Zickzack-Reihenfolge zurück: die Ebene der Wurzel von links nach rechts, die nächste von rechts nach links und so weiter, abwechselnd bis zur tiefsten Ebene. Dies wird auch als spiralförmige Ebenenreihenfolge bezeichnet.
Funktion
- rootinteger-array
- der Baum in Heap-Reihenfolge, mit -1 für eine leere Stelle
- Gibt zurückinteger-2d-array
- eine Liste von Werten pro Ebene, beginnend mit der obersten Ebene, abwechselnd von links nach rechts und von rechts nach links
Einschränkungen
1 ≤ root.length ≤ 32767- Jedes
root[i]ist-1oder ein Wert mit0 ≤ root[i] ≤ 104. - Die Knotenwerte sind eindeutig.
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
14Ebenen.
Beispiele
- Eingabe
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Ausgabe
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Erklärung
- Von links nach rechts gelesen sind die Ebenen
8;12, 5;1, 9, 14;4, 2, 11. Die Ebenen 1 und 3 werden rückwärts durchlaufen:[5, 12]und[11, 2, 4].
- Eingabe
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Ausgabe
- [[1], [3, 2], [4, 5, 6, 7]]
- Erklärung
- Ein vollständiger Baum mit drei Ebenen: Die mittlere Ebene wird zu
[3, 2]umgekehrt, und die dritte verläuft wieder von links nach rechts. Die beiden abschließenden Einträge-1stehen für die leeren Kindpositionen von4.
- Eingabe
- root = [5]
- Ausgabe
- [[5]]
- Erklärung
- Ein einzelner Knoten ist eine Ebene eines Werts, die in beide Richtungen gelesen werden kann.
Weiterführende Frage
Kannst du jeden Wert direkt an seinen endgültigen Platz in seiner Zeile legen, ohne etwas umzukehren und ohne einen zweiten Stapel?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Sammle zunächst die Ebenen von links nach rechts, wie bei einer einfachen Traversierung nach Ebenen. Welche dieser Listen müssen geändert werden, und wie?
Nummeriere die Ebenen beginnend mit 0 an der Wurzel. Die ungeraden Ebenen werden rückwärts gelesen. Eine Liste umzukehren kostet genauso viel wie sie zu lesen. Daher bleibt der Gesamtaufwand linear, wenn du diese Ebenen umkehrst.
Um das Umkehren zu überspringen, behalte die aktuelle Ebene in einem Stack und lege die Kinder beim Entfernen auf einen zweiten Stack: zuerst das linke Kind, wenn du von links nach rechts liest, und zuerst das rechte Kind, wenn du von rechts nach links liest. Der zweite Stack gibt dann die nächste Ebene in der benötigten Reihenfolge aus.
Lösung
Die Ebenen stammen aus einer gewöhnlichen Breitensuche. Neu ist die Richtung: Jede zweite Ebene wird umgekehrt ausgegeben. Kehre entweder die ungeraden Zeilen um, nachdem du sie erstellt hast, oder lege jede Ebene auf einen Stack, der die Elemente in umgekehrter Reihenfolge der Einfügungen zurückgibt.
Ebene für Ebene, dann jede zweite Ebene umkehren
Idee
Eine Warteschlange, die pro Runde eine Ebene verarbeitet, gibt jede Ebene von links nach rechts aus. Nummeriert man die Ebenen ab der Wurzel mit 0, liest die Zickzack-Reihenfolge die ungeraden Ebenen von rechts nach links. Daher erhält man die Antwort, indem man genau diese Zeilen umkehrt.
Die Suche besucht jeden Knoten einmal, und jede Umkehrung berührt jeden Wert ein weiteres Mal. Daher beträgt die Laufzeit O(n).
Algorithmus
- Beginne eine Warteschlange mit dem Index
0. - Speichere für jede Runde die Länge der Warteschlange
s, nimmsIndizes in eine neue Zeile aus der Warteschlange und füge die vorhandenen Kinder jedes Indexes hinzu, zuerst links, dann rechts. - Wenn die Antwort bereits eine ungerade Anzahl von Zeilen enthält, kehre die Zeile um.
- Füge die Zeile hinzu und fahre fort, bis die Warteschlange leer ist.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsZwei Stapel
Idee
Behalte die aktuelle Ebene in einem Stapel, der in der Richtung geleert wird, in der die Ebene gelesen wird, und lege die Kinder jedes entnommenen Knotens auf einen zweiten Stapel. Wenn der aktuelle Stapel leer ist, enthält der zweite die nächste Ebene.
Die Reihenfolge beim Ablegen sorgt dafür, dass es funktioniert. Beim Entnehmen von links nach rechts legst du zuerst das linke und dann das rechte Kind jedes Knotens ab: Das rechte Kind des rechtesten Knotens kommt zuletzt auf den Stapel, sodass die nächste Ebene von ihrem rechten Ende aus entnommen wird. Beim Entnehmen von rechts nach links legst du zuerst das rechte und dann das linke Kind ab, sodass das linke Kind des linkesten Knotens zuletzt auf den Stapel kommt.
Beispiel 1: Entnimm 8, lege 12, 5 ab. Entnimm 5, 12 und lege dann 14 von 5 sowie 9, 1 von 12 ab. Entnimm 1, 9, 14 und lege dann 4, 2 von 9 sowie 11 von 14 ab. Entnimm 11, 2, 4.
Jeder Knoten wird einmal auf den Stapel gelegt und einmal entnommen: Zeitaufwand O(n), ohne Umkehrdurchlauf.
Algorithmus
- Lege den Index
0der Wurzel auf einen Stapel und beginne, von links nach rechts zu lesen. - Solange der Stapel nicht leer ist, nimm jeden Index herunter und füge ihn einer neuen Zeile hinzu. Lege außerdem die vorhandenen Kinder jedes heruntergenommenen Knotens auf einen zweiten Stapel: beim Lesen von links nach rechts zuerst links, dann rechts, andernfalls zuerst rechts, dann links.
- Füge die Zeile der Antwort hinzu.
- Verwende den zweiten Stapel als aktuellen Stapel, kehre die Richtung um und wiederhole den Vorgang.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Stolperfallen und Grenzfälle
- Die Reihenfolge umkehren, in der Kinder in eine einzelne Warteschlange gelangen. Geschwister tauschen die Plätze, aber die Eltern behalten ihre Reihenfolge bei: Die dritte Ebene von Beispiel 1 ergibt
[9, 1, 14]. - Die Ebenen ab 1 zählen. Jede Umkehrung landet eine Ebene daneben, und Beispiel 1 ergibt
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]. - In jeder Ebene dieselbe Reihenfolge beim Hinzufügen in der Zwei-Stapel-Version verwenden. Die dritte Ebene von Beispiel 1 wird dann als
[9, 1, 14]entnommen. - Kinder auf den Stapel legen, von dem du gerade Elemente entnimmst. Sie werden entnommen, bevor der Rest der Ebene ihres Elternknotens an die Reihe kommt.
- Eine Zeile sortieren, statt sie umzukehren. Die letzte Ebene von Beispiel 1 muss
[11, 2, 4]sein, was durch keine Sortierung entsteht.
Häufige Fragen3
Was ist der Unterschied zwischen Zickzack- und Ebenenreihenfolge-Traversierung?
Sie durchlaufen dieselben Ebenen mit denselben Knoten. Die Ebenenreihenfolge liest jede Ebene von links nach rechts; die Zickzack-Reihenfolge liest jede zweite Ebene von rechts nach links, beginnend mit der Ebene unterhalb der Wurzel. Beide laufen in O(n) Zeit.
Ist die Zickzack-Durchquerung dasselbe wie die Spiralreihenfolge-Durchquerung eines Baums?
Ja, die beiden Bezeichnungen beschreiben denselben Durchlauf. In manchen Texten beginnt die zweite Ebene links statt rechts, wodurch sich die Umkehrungen lediglich um eine Ebene verschieben. Hier verläuft die Ebene der Wurzel von links nach rechts und die nächste von rechts nach links.
Kann die Ebenenreihenfolge im Zickzack mit einer Deque umgesetzt werden?
Ja. Behalte jede Ebene in der Deque in der Reihenfolge von links nach rechts bei. Auf einer Ebene von links nach rechts nimmst du die Knoten von vorne und fügst ihre Kinder, zuerst links, dann rechts, hinten hinzu. Auf einer Ebene von rechts nach links nimmst du die Knoten von hinten und fügst ihre Kinder, zuerst rechts, dann links, vorne hinzu. Die Anzahl, die du zu Beginn einer Runde entnimmst, kennzeichnet weiterhin die Ebene.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def zigzagLevelOrder(root):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Erwartete Ausgabe
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]