Kth Smallest Element in a BST
Ricevi un albero binario di ricerca come array root in ordine di heap: la radice si trova all’indice 0, i figli dell’indice i si trovano in 2*i+1 (a sinistra) e 2*i+2 (a destra), e -1 indica una posizione vuota. L’array può terminare con voci -1 aggiuntive. In ogni nodo, il sottoalbero sinistro contiene solo valori minori e quello destro solo valori maggiori.
Restituisci il valore più piccolo numero k nell’albero, contando da 1.
Funzione
- rootinteger-array
- l'albero di ricerca binario in ordine per livelli, con -1 per una posizione vuota
- kinteger
- la posizione da trovare in ordine crescente, a partire da 1
- Restituisceinteger
- il k-esimo valore più piccolo nell'albero
Vincoli
1 ≤ root.length ≤ 32767- Ogni
root[i]è-1oppure un valore con0 ≤ root[i] ≤ 105. root[0]non è mai-1, quindi l'albero ha almeno un nodo.- L’array può terminare con elementi
-1aggiuntivi dopo l’ultimo nodo. - Anche entrambi i figli di una posizione vuota sono vuoti e la profondità è al massimo
14. - La regola di ordinamento vale in ogni nodo, quindi nessun valore compare due volte.
1 ≤ k ≤il numero di nodi nell’albero.
Esempi
- Input
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Output
- 29
- Spiegazione
- In ordine crescente, i valori sono
6, 17, 22, 29, 41, 65, 90e il quarto è29. È il più grande dei quattro valori nel sottoalbero sinistro della radice.
- Input
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Output
- 2
- Spiegazione
- Il valore più piccolo termina il percorso che continua verso sinistra:
12,5,2. Il7sotto9e il padding-1non cambiano questo.
Per approfondire
Se l’albero cambia spesso e ti viene chiesto molte volte il k-esimo valore più piccolo, cosa potrebbe memorizzare ogni nodo affinché ogni query richieda O(h)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Quale modo di attraversare un albero di ricerca binario elenca i suoi valori dal più piccolo al più grande?
Visitare il sottoalbero sinistro, poi il nodo e infine il sottoalbero destro produce un ordine ordinato. Il valore numero
kgenerato da questa visita è la risposta, quindi puoi fermarti lì.Usa uno stack. Dal nodo corrente, inserisci i nodi nello stack mentre ti sposti verso il figlio sinistro. Estrai l'elemento in cima e contalo; fermati alla
k-esima estrazione. Altrimenti, spostati al figlio destro del nodo estratto in2*i+2e ripeti.
Soluzione
Una visita in ordine (sottoalbero sinistro, nodo, sottoalbero destro) legge i valori di un albero di ricerca binario in ordine crescente, quindi il valore in k-esima posizione che raggiunge è la risposta. Esegui la visita usando il tuo stack e fermati lì; non serve ordinare.
Raccogli ogni valore e ordinali
Intuizione
Ignora la struttura: conserva ogni elemento che non sia -1, ordina e restituisci la posizione k-1. Per il primo esempio, la lista ordinata è 6, 17, 22, 29, 41, 65, 90 e alla posizione 3 si trova 29.
È corretto per qualsiasi albero, ordinato o meno. Questo è anche il suo costo: ignora l’ordinamento che l’albero già possiede e paga O(n log n) per l’ordinamento e O(n) di memoria per la copia.
Algoritmo
- Raccogli ogni elemento di
rootche non sia-1. - Ordina i valori raccolti in ordine crescente.
- Restituisci il valore in posizione
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Visita in ordine in una lista
Intuizione
Sotto qualsiasi nodo, il sottoalbero sinistro contiene solo valori più piccoli e quello destro solo valori più grandi. Visita il sottoalbero sinistro, poi il nodo, poi il sottoalbero destro, e fai lo stesso all’interno di ciascun sottoalbero: ogni nodo si trova dopo tutti i valori più piccoli e prima di tutti quelli più grandi, quindi l’output è ordinato. Nel primo esempio, la visita produce 6, 17, 22, 29, 41, 65, 90.
Un’unica passata sostituisce l’ordinamento: tempo O(n) e spazio O(n) per la lista. Visita comunque l’intero albero, anche quando k = 1, in cui la risposta si trova alla fine del percorso più a sinistra.
Algoritmo
- Scrivi
inorder(i): restituisci il risultato in una posizione vuota (oltre la fine o-1). - Altrimenti chiama
inorder(2*i+1), aggiungiroot[i]all'elenco, poi chiamainorder(2*i+2). - Chiama
inorder(0). - Restituisci l'elemento dell'elenco in posizione
k-1.
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 sortedVisita iterativa in ordine simmetrico che si interrompe a k
Intuizione
Uno stack esplicito ti permette di interrompere la visita a metà. Vai a sinistra finché puoi, inserendo ogni nodo. Il nodo in cima è il valore più piccolo non ancora conteggiato, perché tutto ciò che è più piccolo si trova nel suo sottoalbero sinistro, che è vuoto o è già stato conteggiato. Estrai il nodo e conteggialo; il suo sottoalbero destro viene dopo in ordine crescente.
Per k = 4 nel primo esempio: inserisci 41, 17, 6. Estrai 6, poi 17 e passa al suo figlio destro: inserisci 29 e 22. Estrai 22, poi 29, il quarto. La visita non raggiunge mai 65 o 90.
Lo stack contiene al massimo un nodo per livello, quindi lo spazio è O(h). La visita scende una volta e poi estrae k volte: tempo O(h + k).
Algoritmo
- Inizia con uno stack vuoto e
i = 0. - Mentre
iè un nodo reale, inseriscilo nello stack e spostati a2*i+1. - Estrai l'elemento in cima e assegnalo a
i, quindi sottrai1dak. - Se ora
kè0, restituisciroot[i]. - Altrimenti spostati a
2*i+2e torna al passaggio 2.
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
Trappole e casi limite
- Lettura dell'array in ordine degli indici. L'ordine per livelli non è ordinato: il primo esempio inizia con
41, 17, 65. - Errore di un'unità su
k. Si conta a partire da1: restituisci la posizionek-1nell'elenco e interrompi la visita quando il conteggio raggiungek. - Saltare il sottoalbero destro dopo un pop. Nel secondo esempio
9e7si trovano nel sottoalbero destro di5, e la visita non li conterebbe mai. - Considerare reale un figlio mancante. Un figlio è vuoto quando il suo indice supera la fine o contiene
-1:22si trova all'indice9, quindi i suoi figli19e20superano la fine. - Gli array in Lua e R iniziano da 1. Mantieni gli indici dei nodi a base 0 per
2*i+1e leggiroot[i + 1].
Domande frequenti3
Qual è la complessità temporale per trovare il k-esimo elemento più piccolo in un BST?
La visita iterativa in ordine richiede un tempo O(h + k) e uno spazio aggiuntivo O(h) per un albero di profondità h. Nel caso peggiore, k = n oppure l’albero ha la forma di un percorso, cioè O(n).
Come trovi il k-esimo elemento più grande in un BST?
Rispecchia la visita: sottoalbero destro, poi il nodo, poi il sottoalbero sinistro. Questo elenca i valori in ordine decrescente. Vai a destra fin dove puoi mentre inserisci gli elementi nello stack, estrai un elemento e incrementa il conteggio, poi passa al figlio sinistro dopo ogni estrazione. La k-esima estrazione è il k-esimo valore più grande.
Come si interrompe una visita ricorsiva in ordine al k-esimo valore?
Tieni un contatore fuori dalla ricorsione, inizializzato a k. Sottrai 1 dopo che il sottoalbero sinistro di un nodo ha terminato l’esecuzione e registra il valore del nodo quando il contatore raggiunge 0. Dopo ogni chiamata, restituisci subito il controllo se la risposta è stata registrata. La ricorsione corrisponde quindi alla versione con stack: tempo O(h + k), spazio O(h).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def kthSmallest(root, k):
# Scrivi il codice quiTest #1
Test #2
Argomenti
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Output atteso
29