Validate Binary Search Tree
Du erhältst einen Binärbaum, der in dem Array tree in Ebenenreihenfolge gespeichert ist. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am 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 eine Funktion namens isValidBST, die 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. Zwei gleiche Werte können niemals beide in einem gültigen Baum vorkommen.
Funktion
- treeinteger-array
- den Binärbaum in Level-Order-Durchlauf, wobei -1 eine leere Stelle kennzeichnet
- 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.- Hinter dem letzten Knoten kann das Array 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
- Jeder Knoten befindet sich auf der richtigen Seite jedes übergeordneten Knotens. Liest man der Reihe nach (linker Teilbaum, Knoten, rechter Teilbaum), erhält man die Werte
1, 3, 6, 8, 10, 12, 15, streng aufsteigend – genau das liefert ein Suchbaum.
- 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 ist der Baum ungültig. Die
6am Index5befindet sich im rechten Teilbaum der Wurzel10, also muss sie größer als10sein, ist es aber nicht.
- Eingabe
- tree = [12, 7, 12]
- Ausgabe
- false
- Erklärung
- Das rechte Kind der Wurzel enthält
12, denselben Wert wie die Wurzel. Der rechte Teilbaum muss strikt größer sein, daher verletzt ein gleicher Wert die Regel.
+16 versteckte Tests beim Einreichen
Weiterführende Frage
Der Elternknoten des Knotens am Index i befindet sich bei (i-1)/2, abgerundet. Kannst du den Baum in-order mit O(1) zusätzlichem Speicher durchlaufen, indem du dich über die Elternknoten bewegst, statt einen Stack zu verwenden oder rekursiv vorzugehen?
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 der Knoten links von ihm liegt, oberhalb davon, wenn er rechts von ihm liegt. Zusammen bilden diese Grenzen einen offenen Bereich. Geht man von einem Wert
vnach links, wird die obere Grenze aufvgesetzt; geht man nach rechts, wird die untere Grenze aufvgesetzt.Verwende einen Stack aus
(index, low, high), beginnend mit der Wurzel und einem Bereich, der größer ist als jeder zulässige Wert. Entferne einen Eintrag vom Stack, brich ab, wenn der Wert nicht strikt innerhalb des Bereichs liegt, und füge jedes vorhandene Kind mit seinem eingeschränkten Bereich hinzu.
Lösung
Die Regel bezieht sich auf ganze Teilbäume, nicht auf einen Knoten und seine beiden Kinder. Ein Baum kann den Test für Eltern- und Kindknoten an jedem Knoten bestehen und trotzdem falsch sein, weil ein tief liegender Knoten eine Grenze verletzen kann, die ein mehrere Ebenen höher liegender Vorfahr festgelegt hat. Zwei Ansätze lösen das auf elegante Weise: Lies den Baum der Reihe nach aus und prüfe, ob die Werte strikt ansteigen, oder gib jedem Knoten den Wertebereich vor, den seine Vorfahren zulassen, und prüfe ihn anhand dieses Bereichs.
Vergleiche jeden Knoten mit seinen gesamten Teilbäumen
Idee
Zuerst: So bewegst du dich im Array. Der Knoten am Index i hat sein linkes Kind am Index 2*i+1 und sein rechtes Kind am Index 2*i+2. Ein Kind ist nur dann tatsächlich vorhanden, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [10, 5, 15, -1, -1, 6, 20] hat die Wurzel 10 die Werte 5 und 15 an den Indizes 1 und 2, und der Knoten 15 hat die Werte 6 und 20 an den Indizes 5 und 6.
Die erste Idee, die den meisten einfällt, vergleicht jeden Knoten nur mit seinen beiden Kindern. Dieser Baum zeigt, warum das nicht funktioniert: 5 < 10, 15 > 10, 6 < 15 und 20 > 15 gelten alle, aber die 6 befindet sich rechts von 10. Die Definition bezieht sich auf jeden Wert in einem Teilbaum, also prüfe genau das.
Für einen Knoten mit dem Wert v sind alle Werte auf seiner linken Seite genau dann kleiner als v, wenn der größte Wert auf seiner linken Seite kleiner als v ist. Genauso sind alle Werte auf seiner rechten Seite größer als v, wenn der kleinste Wert dort größer als v ist. Zwei kleine rekursive Hilfsfunktionen finden den größten beziehungsweise den kleinsten Wert. Für eine leere Seite ist der größte Wert -1 und der kleinste 100001 – Werte außerhalb des zulässigen Bereichs, sodass eine leere Seite niemals die Prüfung nicht besteht.
Das ist korrekt, führt aber zu wiederholter Arbeit. Ein Knoten wird für jeden Vorfahren über ihm einmal durchlaufen, also gibt es insgesamt etwa n × h Besuche bei einem Baum der Tiefe h. Bei einer Tiefe von höchstens 14 ist das hier in Ordnung, aber bei einem Baum, der aus einem einzigen langen Pfad mit n Knoten besteht, steigt der Aufwand auf O(n²).
Algorithmus
- Gehe jeden Index
idurch, dessen Wert nicht-1ist. - Finde den größten Wert im linken Teilbaum, der bei
2*i+1beginnt, oder-1, wenn diese Stelle leer ist. - Finde den kleinsten Wert im rechten Teilbaum, der bei
2*i+2beginnt, oder100001, wenn diese Stelle leer ist. - Wenn der größte Wert mindestens
tree[i]beträgt oder der kleinste höchstenstree[i]beträgt, gibfalsezurück. - Gib nach dem letzten Knoten
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 ansteigen
Idee
Ein Inorder-Durchlauf besucht den linken Teilbaum, dann den Knoten und anschließend den rechten Teilbaum. In einem binären Suchbaum ist diese Reihenfolge sortiert: Alles links ist kleiner und kommt daher zuerst, und alles rechts ist größer und kommt daher danach. Das erste Beispiel ergibt 1, 3, 6, 8, 10, 12, 15.
Auch die Umkehrung gilt, und genau das macht dies zu einem Test. Nimm einen beliebigen Knoten v. In der Inorder-Sequenz steht sein gesamter linker Teilbaum 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, also gilt die Regel für v und genauso für jeden anderen Knoten.
Durchlaufe also den Baum in Inorder-Reihenfolge, sammle die Werte und vergleiche jeden mit dem davor. Das zweite Beispiel ergibt 5, 10, 6, 15, 20: Der Schritt von 10 hinunter zu 6 zeigt den Knoten auf der falschen Seite. Das dritte ergibt 7, 12, 12, und das wiederholte 12 besteht die strenge Prüfung nicht. Jeder Knoten wird einmal besucht, Laufzeit O(n), und die Liste benötigt O(n) Speicherplatz.
Algorithmus
- Schreibe
walk(i): Wenn der Platz leer ist, stoppe; andernfalls durchlaufe2*i+1, fügetree[i]hinzu und durchlaufe dann2*i+2. - 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
Betrachte die Regel aus der Sicht eines Knotens. Jeder Vorfahr setzt ihm eine Grenze. Befindet sich der Knoten im linken Teilbaum eines Vorfahren mit dem Wert a, muss sein Wert kleiner als a sein; befindet er sich im rechten Teilbaum, muss er größer als a sein. All diese Grenzen bilden zusammen einen offenen Bereich (low, high), und der Knoten ist genau dann an der richtigen Stelle, wenn sein Wert strikt innerhalb dieses Bereichs liegt.
Du kannst diesen Bereich auf dem Weg nach unten aufbauen. Für die Wurzel gibt es keine Grenze. Gehst du von einem Knoten mit dem Wert v zu seinem linken Kind, bleibt low gleich und high wird auf v gesetzt; gehst du zu seinem rechten Kind, bleibt high gleich und low wird auf v gesetzt. Die neue Grenze ist immer enger als die, die sie ersetzt, denn v selbst hat die Prüfung gegen den alten Bereich bestanden.
Im zweiten Beispiel erhält 15 den Bereich (10, no limit) und gibt ihn an sein linkes Kind als (10, 15) weiter. Die 6 liegt unter 10, daher schlägt die Prüfung genau dort fehl, ohne dass ein anderer Knoten betrachtet wird. Die Werte liegen zwischen 0 und 10^5, daher dienen -1 und 100001 als „keine Grenze“.
Lege die noch ausstehenden Knoten zusammen mit ihrem jeweiligen Bereich auf einem Stack ab. Jeder Knoten wird einmal geprüft: Laufzeit O(n), und der Stack enthält die ausstehenden Knoten entlang eines Pfads: Speicherplatz O(h). Der erste ungültige Bereich beendet die Suche.
Algorithmus
- Füge
(0, -1, 100001)hinzu: den Index der Wurzel und einen offenen Bereich ohne echte Grenze. - Entferne
(i, low, high)vom Stapel. Wenntree[i]nicht strikt zwischenlowundhighliegt, gibfalsezurück. - Wenn das linke Kind
2*i+1tatsächlich existiert, füge es mit dem Bereich(low, tree[i])hinzu. - Wenn das rechte Kind
2*i+2tatsächlich existiert, füge es mit dem Bereich(tree[i], high)hinzu. - 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
Die meisten falschen Antworten prüfen zu wenig oder prüfen das Richtige mit dem falschen Vergleich.
- Vergleich eines Knotens nur mit seinen Kindern. In
[10, 5, 15, -1, -1, 6, 20]sieht jedes Eltern-Kind-Paar richtig aus, und die6verletzt trotzdem die Grenze, die die Wurzel zwei Ebenen höher setzt. - Gleiche Werte zulassen. Die Reihenfolge ist auf beiden Seiten strikt, daher ist
[12, 7, 12]nicht gültig. Verwendelow < v < highundvalues[k-1] < values[k], niemals≤. - Nur den Wert des Elternknotens weitergeben. Ein linkes Kind braucht beide Grenzen: kleiner als sein Elternknoten und größer als die untere Grenze, die der Elternknoten hatte. Gib den gesamten Bereich weiter.
- Einen „Grenzwert“ wählen, den ein Knoten haben kann. Werte beginnen bei
0, daher würde eine untere Grenze von0einen gültigen Knoten mit dem Wert0ablehnen, wie in[0]. Beginne unterhalb aller zulässigen Werte. - Über das Ende des Arrays hinaus lesen. Prüfe
2*i+1 < tree.length, bevor du ein Kind liest, und behandle-1als kein Kind. - Den Offset in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte die 0-basierte Indizierung der Knoten für die Rechnung mit
2*i+1bei und liestree[i + 1].
Häufige Fragen4
Warum reicht es nicht aus, jeden Knoten mit seinen Kindern zu vergleichen, um einen BST zu überprüfen?
Die Regel gilt für ganze Teilbäume. Ein Knoten tief im rechten Teilbaum der Wurzel muss größer als die Wurzel sein, selbst wenn er das linke Kind eines viel größeren Knotens ist. In [10, 5, 15, -1, -1, 6, 20] ist die 6 ein passendes linkes Kind von 15, befindet sich aber rechts von 10, daher ist der Baum kein Suchbaum. Du brauchst die Grenzen aller Vorfahren, nicht nur des Elternknotens.
Wie hoch ist die Zeitkomplexität beim Validieren eines binären Suchbaums?
Beide Standardmethoden, die In-Order-Prüfung und die Bereichsprüfung, betrachten jeden Knoten einmal und benötigen daher O(n) Zeit. Die Bereichsprüfung benötigt O(h) zusätzlichen Speicherplatz für den Stack, wobei h die Tiefe ist. Jeder Knoten mit seinen gesamten Teilbäumen zu vergleichen, funktioniert ebenfalls, kostet aber O(n × h), was bei einem baumförmigen Pfad O(n²) erreicht.
Kannst du einen BST mit einer Inorder-Traversierung validieren, ohne jeden Wert zu speichern?
Ja. Die Inorder-Prüfung vergleicht einen Wert immer nur mit dem unmittelbar vorherigen, daher speicherst du den vorherigen Wert in einer Variablen statt in einer Liste. Durchlaufe den Baum in Inorder-Reihenfolge rekursiv oder mit einem expliziten Stack und gib false zurück, sobald ein Wert nicht größer als der vorherige ist. Dadurch sinkt der zusätzliche Speicherbedarf auf O(h).
Darf ein binärer Suchbaum doppelte Werte enthalten?
Nicht nach der hier verwendeten strengen Definition: Jeder linke Wert muss kleiner und jeder rechte größer sein, daher können niemals zwei gleiche Werte gleichzeitig passen. Manche Lehrbücher erlauben Duplikate auf einer Seite, zum Beispiel gleiche Werte rechts. Nach dieser Regel würdest du einen strengen Vergleich in ≤ ändern. Lies also die Definition, bevor du die Prüfung schreibst.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def isValidBST(tree):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
tree = [8, 3, 12, 1, 6, 10, 15]
Erwartet
true