Kth Smallest Element in a BST
Du erhältst einen binären Suchbaum als Array root in Heap-Reihenfolge: Die Wurzel befindet sich am Index 0, die Kinder des Index i befinden sich bei 2*i+1 (links) und 2*i+2 (rechts), und -1 kennzeichnet eine leere Stelle. Das Array kann mit zusätzlichen -1-Einträgen enden. Bei jedem Knoten enthält der linke Teilbaum nur kleinere Werte und der rechte Teilbaum nur größere Werte.
Gib den k-kleinsten Wert im Baum zurück, wobei ab 1 gezählt wird.
Funktion
- rootinteger-array
- der binäre Suchbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
- kinteger
- die zu findende Position in aufsteigender Reihenfolge, beginnend bei 1
- Gibt zurückinteger
- der k-kleinste Wert im Baum
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. - Die Ordnungsregel gilt an jedem Knoten, daher kommt kein Wert doppelt vor.
1 ≤ k ≤die Anzahl der Knoten im Baum.
Beispiele
- Eingabe
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Ausgabe
- 29
- Erklärung
- In aufsteigender Reihenfolge lauten die Werte
6, 17, 22, 29, 41, 65, 90, und der vierte ist29. Er ist der größte der vier Werte im linken Teilbaum der Wurzel.
- Eingabe
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Ausgabe
- 2
- Erklärung
- Der kleinste Wert beendet den Pfad, der immer weiter nach links führt:
12,5,2. Die7unter9und die Auffüllung mit-1ändern daran nichts.
Weiterführende Frage
Wenn sich der Baum häufig ändert und du oft nach dem k-kleinsten Wert gefragt wirst, was könnte jeder Knoten speichern, damit jede Abfrage O(h) benötigt?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Welche Art, einen binären Suchbaum zu durchlaufen, listet seine Werte vom kleinsten zum größten auf?
Das Durchlaufen des linken Teilbaums, dann des Knotens und anschließend des rechten Teilbaums ergibt eine sortierte Reihenfolge. Der
k-te Wert, den dieser Durchlauf liefert, ist die Antwort, also kannst du dort aufhören.Verwende einen Stapel. Schiebe ausgehend vom aktuellen Knoten Knoten auf den Stapel, während du zum linken Kind gehst. Nimm das oberste Element herunter und zähle es; stoppe beim
k-ten Entnehmen. Andernfalls gehe zum rechten Kind des entnommenen Knotens bei2*i+2und wiederhole den Vorgang.
Lösung
Ein Inorder-Durchlauf (linker Teilbaum, Knoten, rechter Teilbaum) liest die Werte eines binären Suchbaums in aufsteigender Reihenfolge, sodass der k-te erreichte Wert die Antwort ist. Führe den Durchlauf mit einem eigenen Stack aus und halte dort an; eine Sortierung ist nicht nötig.
Sammle alle Werte und sortiere sie
Idee
Ignoriere die Form: Behalte jeden Eintrag bei, der nicht -1 ist, sortiere und gib die Position k-1 zurück. Für das erste Beispiel lautet die sortierte Liste 6, 17, 22, 29, 41, 65, 90, und an Position 3 steht 29.
Das ist für jeden Baum korrekt, ob geordnet oder nicht. Das ist auch der Preis dafür: Die bereits vorhandene Ordnung des Baums wird ignoriert, und für das Sortieren fallen O(n log n) sowie für die Kopie O(n) Speicher an.
Algorithmus
- Sammle jeden Eintrag von
root, der nicht-1ist. - Sortiere die gesammelten Werte in aufsteigender Reihenfolge.
- Gib den Wert an Position
k-1zurück.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Inorder-Traversierung in eine Liste
Idee
Unterhalb jedes Knotens enthält der linke Teilbaum nur kleinere Werte und der rechte Teilbaum nur größere. Durchlaufe den linken Teilbaum, dann den Knoten und anschließend den rechten Teilbaum und verfahre in jedem Teilbaum genauso: Jeder Knoten steht nach allen kleineren Werten und vor allen größeren, sodass die Ausgabe sortiert ist. Im ersten Beispiel ergibt der Durchlauf 6, 17, 22, 29, 41, 65, 90.
Ein einziger Durchlauf ersetzt das Sortieren: Zeitaufwand O(n) und Speicherplatz O(n) für die Liste. Dabei wird weiterhin der gesamte Baum durchlaufen, selbst bei k = 1, wenn die Antwort am Ende des ganz linken Pfads steht.
Algorithmus
- Schreibe
inorder(i): Kehre bei einer leeren Stelle zurück (hinter dem Ende oder-1). - Rufe andernfalls
inorder(2*i+1)auf, fügeroot[i]der Liste hinzu und rufe danninorder(2*i+2)auf. - Rufe
inorder(0)auf. - Gib den Listeneintrag an Position
k-1zurück.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedIterative Inorder-Traversierung, die bei k stoppt
Idee
Ein expliziter Stack ermöglicht es dir, den Durchlauf mittendrin zu beenden. Gehe so weit wie möglich nach links und lege dabei jeden Knoten auf den Stack. Der oberste Knoten enthält den kleinsten noch nicht gezählten Wert, denn alles Kleinere befindet sich in seinem linken Teilbaum, der leer ist oder bereits gezählt wurde. Nimm ihn vom Stack und zähle ihn; sein rechter Teilbaum kommt als Nächstes in sortierter Reihenfolge.
Für k = 4 im ersten Beispiel: Lege 41, 17, 6 auf den Stack. Nimm 6 und dann 17 vom Stack und gehe zu dessen rechtem Kind: Lege 29 und 22 auf den Stack. Nimm 22 und dann 29, den vierten Wert, vom Stack. Der Durchlauf berührt weder 65 noch 90.
Der Stack enthält höchstens einen Knoten pro Ebene, daher beträgt der Speicherbedarf O(h). Der Durchlauf geht einmal nach unten und nimmt dann k Knoten vom Stack: Laufzeit O(h + k).
Algorithmus
- Beginne mit einem leeren Stapel und
i = 0. - Solange
iein echter Knoten ist, lege ihn auf den Stapel und gehe zu2*i+1. - Nimm das oberste Element vom Stapel und speichere es in
i; ziehe1vonkab. - Wenn
kjetzt0ist, gibroot[i]zurück. - Gehe andernfalls zu
2*i+2und fahre mit Schritt 2 fort.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Stolperfallen und Grenzfälle
- Das Array in Indexreihenfolge durchlaufen. Die Ebenenreihenfolge ist nicht sortiert: Das erste Beispiel beginnt mit
41, 17, 65. - Ein Off-by-one-Fehler bei
k. Die Zählung beginnt bei1: Gib die Listenpositionk-1zurück und beende den Durchlauf, wenn die Zählungkerreicht. - Den rechten Teilbaum nach einem Entfernen überspringen. Im zweiten Beispiel befinden sich
9und7im rechten Teilbaum von5, und beim Durchlauf würden sie nie gezählt. - Ein fehlendes Kind als vorhanden behandeln. Ein Kind ist leer, wenn sein Index außerhalb des Arrayendes liegt oder den Wert
-1enthält:22befindet sich an Index9, daher liegen seine Kinder19und20außerhalb des Arrayendes. - Lua- und R-Arrays beginnen bei 1. Behalte für
2*i+1die 0-basierten Knotenindizes bei und liesroot[i + 1].
Häufige Fragen3
Wie hoch ist die Zeitkomplexität beim Finden des k-kleinsten Elements in einem BST?
Der iterative Inorder-Durchlauf benötigt bei einem Baum der Tiefe h O(h + k) Zeit und O(h) zusätzlichen Speicherplatz. Im ungünstigsten Fall gilt k = n oder der Baum ist pfadförmig; dann beträgt der Aufwand O(n).
Wie findest du das k-größte Element in einem BST?
Spiegle den Durchlauf: zuerst den rechten Teilbaum, dann den Knoten und anschließend den linken Teilbaum. Dadurch werden die Werte in absteigender Reihenfolge aufgelistet. Gehe so weit wie möglich nach rechts und füge dabei Knoten zum Stack hinzu, entnimm dann einen Knoten und zähle mit. Gehe nach jeder Entnahme zum linken Kind. Die k-te Entnahme ist der k-größte Wert.
Wie stoppst du eine rekursive Inorder-Traversierung beim k-ten Wert?
Führe außerhalb der Rekursion einen Zähler, der bei k beginnt. Ziehe 1 ab, nachdem der linke Teilbaum eines Knotens zurückgekehrt ist, und speichere den Wert des Knotens, wenn der Zähler 0 erreicht. Kehre nach jedem Aufruf sofort zurück, wenn die Antwort gespeichert ist. Die Rekursion entspricht dann der Stack-Version: O(h + k) Zeit, O(h) Speicherplatz.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def kthSmallest(root, k):
# Schreibe hier CodeTest #1
Test #2
Argumente
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Erwartete Ausgabe
29