Boundary Traversal of Binary Tree
Das Array root enthält einen Binärbaum in Ebenenreihenfolge: die Wurzel an Index 0, die Kinder von Index i an den Indizes 2i+1 (links) und 2i+2 (rechts), -1 für eine leere Stelle und möglicherweise zusätzliche -1-Einträge am Ende. Ein Blatt ist ein Knoten ohne Kinder.
Gib den Rand gegen den Uhrzeigersinn von der Wurzel aus zurück:
- Die Wurzel.
- Der linke Rand, von oben nach unten: Beginne beim linken Kind der Wurzel und gehe zum linken Kind, falls vorhanden, andernfalls zum rechten Kind. Höre vor einem Blatt auf.
- Jedes Blatt, von links nach rechts.
- Der rechte Rand, von unten nach oben: das Spiegelbild des linken Randes, beginnend beim rechten Kind der Wurzel.
Kein Knoten wird zweimal aufgeführt, daher besteht ein Baum mit nur einem Knoten ausschließlich aus seiner Wurzel.
Funktion
- rootinteger-array
- der Binärbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
- Gibt zurückinteger-array
- die Randwerte, gegen den Uhrzeigersinn von der Wurzel aus
Einschränkungen
1 ≤ root.length ≤ 32767- Jedes
root[i]ist-1oder ein Wert mit0 ≤ root[i] ≤ 105. 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 eines leeren Platzes sind ebenfalls leer, und die Tiefe beträgt höchstens
14. - Knotenwerte sind verschieden.
Beispiele
- Eingabe
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Ausgabe
- [7, 3, 1, 4, 6, 8, 9]
- Erklärung
- Nach der Wurzel
7ist die linke Grenze3: Ihr Kind1ist ein Blatt. Die Blätter sind1,4,6,8. Die rechte Grenze ist9, oberhalb des Blatts8.
- Eingabe
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Ausgabe
- [10, 4, 6, 5, 8]
- Erklärung
4hat kein linkes Kind, daher wendet sich die linke Grenze6zu und endet dann beim Blatt5. Es folgen die Blätter5,8. Die Wurzel hat kein rechtes Kind.
- Eingabe
- root = [3]
- Ausgabe
- [3]
- Erklärung
- Die Wurzel ist der gesamte Baum. Sie wird einmal aufgeführt, nicht noch einmal als Blatt.
Weiterführende Frage
Wie würdest du den Rand im Uhrzeigersinn auflisten: die Wurzel, die rechte Kante von oben nach unten, die Blätter von rechts nach links und dann die linke Kante von unten nach oben?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Teile die Antwort in vier Teile auf: die Wurzel, den linken Rand, die Blätter und den rechten Rand. Welche davon bilden einen einzelnen Pfad durch den Baum nach unten, und welche erfordern eine vollständige Durchquerung?
Jede Kante ist ein Pfad: Gehe vom Kind der Wurzel aus immer weiter zum Kind auf dieser Seite oder zum anderen Kind, wenn diese Seite leer ist. Die Blätter in der Reihenfolge von links nach rechts ergeben sich aus einer Tiefensuche, die zuerst den linken Teilbaum besucht. Achte auf die Verbindungen: Das Blatt, an dem eine Kante endet, gehört zu den Blättern.
Gehe von Index
1abwärts und füge jeden Nicht-Blattknoten hinzu. Füge dann jedes Blatt bei einem Präorder-Durchlauf hinzu. Gehe anschließend von Index2abwärts, sammle jeden Nicht-Blattknoten und füge diese Liste in umgekehrter Reihenfolge hinzu.
Lösung
Die Antwort setzt sich aus vier Teilen zusammen: der Wurzel, einem Pfad entlang der linken Kante, den Blättern von links nach rechts und einem Pfad entlang der rechten Kante, rückwärts gelesen. An den Übergängen müssen ein Blatt, das eine Kante abschließt, und eine Wurzel, die ein Blatt ist, jeweils nur einmal aufgeführt werden.
Gehe die drei Teile getrennt durch
Idee
Jeder Randabschnitt ist ein Pfad: Beginne beim Kind der Wurzel und liste die Knoten auf, bis der nächste ein Blatt wäre, das stattdessen im Blattteil aufgeführt wird. Ein Präorder-Durchlauf, der zuerst nach links und dann nach rechts geht, trifft die Blätter von links nach rechts, denn alle Knoten eines linken Teilbaums liegen links vom rechten Teilbaum, unabhängig von ihrer Tiefe. Erfasse den rechten Rand von oben nach unten und hänge ihn umgekehrt an.
Die Ränder folgen jeweils einem Pfad, und der Blattdurchlauf besucht jeden Knoten genau einmal: O(n) Zeit, bei einer Rekursionstiefe von h Ebenen.
Algorithmus
- Beginne bei der Wurzel; wenn sie ein Blatt ist, gib sie zurück.
- Beginne bei Index
1. Solange der Knoten existiert und kein Blatt ist, füge ihn hinzu und gehe zu seinem linken Kind oder, falls es kein linkes Kind gibt, zu seinem rechten Kind. - Durchlaufe den Baum in Preorder, zuerst links, beginnend bei den Indizes
1und2, und füge jedes Blatt hinzu. - Führe ab Index
2dasselbe wie in Schritt 2 aus, bevorzuge dabei aber rechte Kinder und sammle die Knoten. - Füge die gesammelten Knoten in umgekehrter Reihenfolge hinzu.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultEin Preorder-Durchlauf mit Kantenmarkierungen
Idee
Fasse die Durchläufe zu einem einzigen Preorder-Durchlauf auf einem Stack zusammen, indem du jedem Knoten ein Flag zuweist: 1 am linken Rand, 2 am rechten Rand, 0 im Inneren. Die Kinder der Wurzel beginnen mit 1 und 2. Ein Randknoten gibt sein Flag an das Kind auf seiner Seite oder an sein einziges Kind weiter; jedes andere Kind erhält 0. Im zweiten Beispiel wird 1 von 4 über 6 an 5 weitergegeben.
Wenn Knoten vom Stack genommen werden, füge jedes Blatt und jeden Nicht-Blatt-Knoten mit dem Flag 1 hinzu; sammle die Nicht-Blatt-Knoten mit dem Flag 2 und füge sie am Ende in umgekehrter Reihenfolge hinzu. Bei der Preorder wird jeder Knoten am linken Rand vor jedem Blatt erreicht, weil der Rand nur dort nach rechts abbiegt, wo nichts links davon liegt.
Algorithmus
- Beginne mit der Wurzel. Lege ihr rechtes Kind mit Flagge
2und dann ihr linkes Kind mit Flagge1auf den Stapel. - Nimm einen Knoten vom Stapel. Hänge ihn an, wenn er ein Blatt ist oder die Flagge
1hat; füge einen Nicht-Blatt-Knoten mit Flagge2zur rechten Liste hinzu. - Lege sein rechtes Kind und dann sein linkes Kind auf den Stapel, jeweils mit der Flagge, die ihm die Regel zuweist.
- Wenn der Stapel leer ist, hänge die rechte Liste in umgekehrter Reihenfolge an.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Stolperfallen und Grenzfälle
- Einen Knoten zweimal auflisten. Ein Randdurchlauf, der nicht vor seinem Blatt endet, listet im Beispiel 1
1zweimal auf, und ein Baum mit nur einem Knoten darf seine Wurzel nicht erneut als Blatt auflisten. - Den ersten Knoten jeder Ebene als linken Rand nehmen. Wenn das linke Kind der Wurzel ein Blatt ist und der rechte Teilbaum tiefer reicht, beginnen die tieferen Ebenen mit Knoten des rechten Teilbaums, obwohl der linke Rand leer ist.
- Nur linken Kindern folgen. Im Beispiel 2 muss der Rand von
4zu seinem rechten Kind6verlaufen. - Blätter Ebene für Ebene sammeln. Beispiel 1 ergibt dann
1,8,4,6. - In Lua und R die Knotenindizes für die Rechnung mit
2i+1bei 0 beginnen lassen undroot[i + 1]lesen.
Häufige Fragen3
Was ist die Randdurchquerung eines binären Baums?
Sie listet die Umrandung des Baums gegen den Uhrzeigersinn auf: die Wurzel, die linke Kante von oben nach unten, die Blätter von links nach rechts und die rechte Kante von unten nach oben. Die Kanten lassen ihre Blätter aus, sodass kein Knoten zweimal erscheint.
Wie hoch ist die Zeitkomplexität der Randdurchquerung?
O(n). Die beiden Randdurchläufe folgen jeweils einem Pfad, und der Blattdurchlauf besucht jeden Knoten genau einmal. Der zusätzliche Speicherbedarf beträgt O(h) für die Rekursion oder den Stack.
Folgt die linke Begrenzung immer den linken Kindern?
Nein. Sie geht zum linken Kind, wenn eines vorhanden ist, und andernfalls zum rechten Kind: der äußerste Pfad, den du von links aus siehst. Wenn die Wurzel kein linkes Kind hat, ist die linke Begrenzung leer.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def boundaryTraversal(root):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Erwartete Ausgabe
[7, 3, 1, 4, 6, 8, 9]