Validate Binary Search Tree
Ein Binärbaum wird im Heap-Format im Array tree 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.
Schreibe isValidBST, das true zurückgibt, wenn der Baum ein binärer Suchbaum ist, und andernfalls false. In einem binären Suchbaum ist der Wert jedes Knotens strikt größer als jeder Wert in seinem linken Teilbaum und strikt kleiner als jeder Wert in seinem rechten Teilbaum.
Funktion
- treeinteger-array
- der Binärbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
- Gibt zurückboolean
- wahr, wenn der Baum ein binärer Suchbaum ist, andernfalls falsch
Einschränkungen
1 ≤ tree.length ≤ 32767- Jedes
tree[i]ist-1oder ein Wert mit0 ≤ tree[i] ≤ 105. tree[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 die Tiefe beträgt höchstens
14. - Werte können sich wiederholen.
Beispiele
- Eingabe
- tree = [8, 3, 12, 1, 6, 10, 15]
- Ausgabe
- true
- Erklärung
- Liest man in dieser Reihenfolge (linker Teilbaum, Knoten, rechter Teilbaum), lauten die Werte
1, 3, 6, 8, 10, 12, 15. Sie steigen streng an, sodass jeder Knoten auf der richtigen Seite jedes Vorfahren liegt.
- Eingabe
- tree = [10, 5, 15, -1, -1, 6, 20]
- Ausgabe
- false
- Erklärung
- Jeder Knoten ist größer als sein linkes Kind und kleiner als sein rechtes Kind, dennoch befindet sich die
6am Index5im rechten Teilbaum der Wurzel und muss daher größer als10sein.
- Eingabe
- tree = [12, 7, 12]
- Ausgabe
- false
- Erklärung
- Das rechte Kind der Wurzel enthält
12, was dem Wert der Wurzel entspricht. Der rechte Teilbaum muss strikt größer sein, daher ist der Baum ungültig.
Weiterführende Frage
Der Elternknoten eines Knotens befindet sich am Index (i-1)/2, abgerundet. Kannst du den Baum der Reihe nach mit zusätzlichem Speicherplatz von O(1) durchlaufen und dich dabei über die Elternknoten statt über einen Stack oder Rekursion bewegen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
In
[10, 5, 15, -1, -1, 6, 20]ist jeder Knoten größer als sein linkes Kind und kleiner als sein rechtes Kind. Warum ist es trotzdem kein Suchbaum?Jeder Vorfahr setzt einem Knoten eine Grenze: unterhalb davon, wenn sich der Knoten links befindet, oberhalb davon, wenn er rechts ist. Zusammen bilden diese Grenzen einen offenen Bereich. Beim Gang nach links von einem Wert
vwird die obere Grenze aufvgesetzt; beim Gang nach rechts wird die untere Grenze aufvgesetzt.Lege einen Stapel aus
(index, low, high)an, beginnend mit der Wurzel und einem Bereich, der alle zulässigen Werte umfasst. Entferne einen Eintrag, brich ab, wenn der Wert nicht strikt innerhalb des Bereichs liegt, und lege jedes tatsächlich vorhandene Kind mit seinem eingeengten Bereich auf den Stapel.
Lösung
Die Regel gilt für ganze Teilbäume. Daher reicht es nicht aus, jeden Knoten mit seinen beiden Kindern zu vergleichen: Ein Knoten tief unten kann eine Grenze verletzen, die ein Vorfahr mehrere Ebenen weiter oben festgelegt hat. Lies den Baum entweder der Reihe nach aus und prüfe, ob die Werte streng ansteigen, oder übergib jedem Knoten den Wertebereich, den seine Vorfahren zulassen.
Vergleiche jeden Knoten mit seinen gesamten Teilbäumen
Idee
Jeder Wert links von einem Knoten liegt genau dann unter seinem Wert v, wenn der größte Wert dort unter v liegt, und jeder Wert rechts von ihm liegt genau dann über v, wenn der kleinste Wert dort über v liegt. Zwei rekursive Hilfsfunktionen ermitteln diese Werte. Eine leere Seite gibt -1 oder 100001 zurück, also einen Wert außerhalb des Wertebereichs, sodass die Prüfung niemals fehlschlägt.
Jeder Knoten wird für jeden seiner Vorfahren einmal durchlaufen, also etwa n × h Besuche bei einem Baum der Tiefe h. Bei einer Tiefe von höchstens 14 ist das günstig, aber bei einem Pfad aus n Knoten wächst der Aufwand auf O(n²).
Algorithmus
- Gehe jeden Index
idurch, dessen Wert nicht-1ist. - Finde den größten Wert im linken Teilbaum bei
2*i+1(-1, wenn er leer ist) und den kleinsten im rechten Teilbaum bei2*i+2(100001, wenn er leer ist). - Wenn der größte Wert mindestens
tree[i]beträgt oder der kleinste höchstenstree[i]beträgt, gibfalsezurück. - Gib
truezurück.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return TrueDie Werte bei einer Inorder-Traversierung müssen streng monoton ansteigen
Idee
Ein Inorder-Durchlauf besucht den linken Teilbaum, dann den Knoten und anschließend den rechten Teilbaum. In einem binären Suchbaum liest er die Werte daher in sortierter Reihenfolge aus.
Auch die Umkehrung gilt. Für jeden Knoten v kommt sein gesamter linker Teilbaum in der Sequenz direkt davor und sein gesamter rechter Teilbaum direkt danach. Wenn die Sequenz streng ansteigt, ist jeder Wert vor v kleiner und jeder Wert danach größer. Somit gilt die Regel für v und ebenso für jeden anderen Knoten.
Das zweite Beispiel ergibt 5, 10, 6, 15, 20: Der Abfall von 10 auf 6 deckt den falsch platzierten Knoten auf. Jeder Knoten wird einmal besucht: Zeitaufwand O(n) und Speicherplatzbedarf O(n) für die Liste.
Algorithmus
- Schreibe
walk(i): Wenn die Stelle leer ist, beende die Funktion; andernfalls gehe2*i+1durch, fügetree[i]hinzu und gehe dann2*i+2durch. - Rufe
walk(0)auf, um die Werte der Reihe nach zu sammeln. - Prüfe für jede Position
kab1: Wennvalues[k-1] ≥ values[k], gibfalsezurück. - Gib
truezurück.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return TrueDen zulässigen Wertebereich im Baum nach unten weitergeben
Idee
Jeder Vorfahr setzt eine Grenze für einen Knoten: unter a, wenn sich der Knoten im linken Teilbaum eines Vorfahren mit dem Wert a befindet, über a, wenn er sich im rechten Teilbaum befindet. Zusammen bilden die Grenzen einen offenen Bereich (low, high), und der Knoten befindet sich genau dann an der richtigen Stelle, wenn sein Wert strikt innerhalb dieses Bereichs liegt.
Baue den Bereich auf dem Weg nach unten auf. Ein linkes Kind behält low und erhält high = v; ein rechtes Kind behält high und erhält low = v. Im zweiten Beispiel übergibt 15 seinem linken Kind den Bereich (10, 15), und die 6 fällt sofort durch. Die Werte liegen zwischen 0 und 10^5, daher dienen -1 und 100001 als Grenzenlosigkeitswerte. Jeder Knoten wird einmal geprüft, in O(n) Zeit, mit O(h) Knoten auf dem Stack.
Algorithmus
- Lege
(0, -1, 100001)auf den Stapel: die Wurzel, ohne echte Grenze. - Nimm
(i, low, high)vom Stapel. Wenntree[i]nicht strikt zwischenlowundhighliegt, gibfalsezurück. - Lege jedes vorhandene Kind auf den Stapel: das linke bei
2*i+1mit(low, tree[i]), das rechte bei2*i+2mit(tree[i], high). - Wenn der Stapel leer ist, gib
truezurück.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
Stolperfallen und Grenzfälle
- Vergleich eines Knotens nur mit seinen Kindern. In
[10, 5, 15, -1, -1, 6, 20]sieht jedes Eltern-Kind-Paar richtig aus, doch die6verletzt die Grenze der Wurzel. - Gleich große Werte zulassen.
[12, 7, 12]ist ungültig: Vergleiche mit<, niemals mit≤. 0als untere Grenze für „keine Grenze“ verwenden. Dadurch wird der gültige Baum[0]abgelehnt.- Ein Kind lesen, ohne
2*i+1 < tree.lengthzu prüfen. In[12, 7, 12]liegt der Index3hinter dem Ende. - In Lua und R beginnen Arrays bei 1. Behalte die Knotenindizes für
2*i+1bei 0 und liestree[i + 1].
Häufige Fragen3
Wie hoch ist die Zeitkomplexität beim Überprüfen eines binären Suchbaums?
Die Inorder-Prüfung und die Bereichsprüfung besuchen jeden Knoten einmal: Laufzeit O(n), wobei die Bereichsprüfung auf einem Baum der Tiefe h zusätzlichen Speicherplatz von O(h) für den Stack benötigt. Jeder Knoten mit seinen gesamten Teilbäumen zu vergleichen, kostet O(n × h), was bei einem wie ein Pfad geformten Baum O(n²) erreicht.
Kannst du einen BST mit einer Inorder-Traversierung validieren, ohne jeden Wert zu speichern?
Ja. Die Prüfung vergleicht jeden Wert nur mit dem vorherigen. Speichere den vorherigen Wert daher in einer Variablen statt in einer Liste und gib sofort false zurück, sobald ein Wert nicht größer ist. Der zusätzliche Speicherplatz sinkt bei der Rekursion oder dem Stack auf O(h).
Kann ein binärer Suchbaum doppelte Werte enthalten?
Nicht nach der hier verwendeten strengen Definition: Ein gleicher Wert passt auf keine der beiden Seiten. Manche Lehrbücher erlauben gleiche Werte auf einer Seite, zum Beispiel rechts. Nach dieser Regel wird ein strenger Vergleich zu ≤.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def isValidBST(tree):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
tree = [8, 3, 12, 1, 6, 10, 15]
Erwartete Ausgabe
true