Validate Binary Search Tree
Un albero binario è memorizzato nell’array tree in ordine heap: la radice si trova all’indice 0, i figli dell’indice i si trovano a 2*i+1 (sinistro) e 2*i+2 (destro), -1 indica una posizione vuota e l’array può terminare con ulteriori elementi -1.
Scrivi isValidBST, che restituisce true se l’albero è un albero binario di ricerca e false altrimenti. In un albero binario di ricerca, il valore di ogni nodo è strettamente maggiore di ogni valore del suo sottoalbero sinistro e strettamente minore di ogni valore del suo sottoalbero destro.
Funzione
- treeinteger-array
- l'albero binario in ordine per livelli, con -1 per una posizione vuota
- Restituisceboolean
- vero se l'albero è un albero binario di ricerca, falso altrimenti
Vincoli
1 ≤ tree.length ≤ 32767- Ogni
tree[i]è-1oppure un valore con0 ≤ tree[i] ≤ 105. tree[0]non è mai-1, quindi l'albero ha almeno un nodo.- L'array può terminare con voci
-1aggiuntive dopo l'ultimo nodo. - Entrambi i figli di un punto vuoto sono vuoti a loro volta e la profondità è al massimo
14. - I valori possono ripetersi.
Esempi
- Input
- tree = [8, 3, 12, 1, 6, 10, 15]
- Output
- true
- Spiegazione
- Leggendo in ordine (sottoalbero sinistro, nodo, sottoalbero destro), i valori sono
1, 3, 6, 8, 10, 12, 15. Aumentano strettamente, quindi ogni nodo si trova dal lato corretto rispetto a ogni antenato.
- Input
- tree = [10, 5, 15, -1, -1, 6, 20]
- Output
- false
- Spiegazione
- Ogni nodo è più grande del suo figlio sinistro e più piccolo del suo figlio destro, eppure il
6all’indice5si trova nel sottoalbero destro della radice, quindi deve essere più grande di10.
- Input
- tree = [12, 7, 12]
- Output
- false
- Spiegazione
- Il figlio destro della radice contiene
12, uguale alla radice. Il sottoalbero destro deve essere strettamente maggiore, quindi l'albero non è valido.
Per approfondire
Il genitore di un nodo si trova all’indice (i-1)/2, arrotondato per difetto. Riesci ad attraversare l’albero in ordine usando O(1) spazio aggiuntivo, spostandoti tra i genitori invece di usare uno stack o la ricorsione?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
In
[10, 5, 15, -1, -1, 6, 20], ogni nodo è maggiore del suo figlio sinistro e minore del suo figlio destro. Perché non è comunque un albero di ricerca?Ogni antenato impone un limite a un nodo: inferiore se il nodo si trova alla sua sinistra, superiore se si trova alla sua destra. Insieme, questi limiti formano un intervallo aperto. Andare a sinistra da un valore
vabbassa il limite superiore av; andare a destra alza il limite inferiore av.Mantieni uno stack di
(index, low, high), iniziando dalla radice e con un intervallo più ampio di ogni valore consentito. Estrai una voce, fallisci se il valore non è strettamente all’interno dell’intervallo e inserisci ogni figlio effettivo con il relativo intervallo ristretto.
Soluzione
La regola riguarda interi sottoalberi, quindi confrontare ogni nodo con i suoi due figli non è sufficiente: un nodo in profondità può violare un limite stabilito da un antenato diversi livelli più in alto. Puoi leggere l’albero in ordine e verificare che i valori aumentino strettamente, oppure passare a ogni nodo l’intervallo consentito dai suoi antenati.
Confronta ogni nodo con i suoi interi sottoalberi
Intuizione
Ogni valore a sinistra di un nodo è minore del suo valore v esattamente quando il valore più grande in quella parte è minore di v, e ogni valore a destra di v è maggiore esattamente quando il valore più piccolo in quella parte è maggiore di v. Due funzioni ricorsive di supporto li trovano. Un lato vuoto restituisce -1 o 100001, valori fuori dall’intervallo dei valori, quindi non fa mai fallire il controllo.
Ogni nodo viene esaminato una volta per ciascun antenato: circa n × h visite per un albero di profondità h. Con una profondità al massimo pari a 14, è un costo contenuto, ma in un percorso di n nodi cresce fino a O(n²).
Algoritmo
- Esamina ogni indice
iil cui valore non è-1. - Trova il valore più grande nel sottoalbero sinistro in
2*i+1(-1se vuoto) e il più piccolo nel sottoalbero destro in2*i+2(100001se vuoto). - Se il valore più grande è maggiore o uguale a
tree[i], oppure il più piccolo è minore o uguale atree[i], restituiscifalse. - Restituisci
true.
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 TrueI valori in ordine simmetrico devono aumentare strettamente
Intuizione
Una visita in ordine visita il sottoalbero sinistro, poi il nodo e infine il sottoalbero destro, quindi in un albero binario di ricerca legge i valori in ordine crescente.
Vale anche il viceversa. Per qualsiasi nodo v, tutto il suo sottoalbero sinistro viene subito prima di esso nella sequenza e tutto il suo sottoalbero destro subito dopo. Se la sequenza è strettamente crescente, ogni valore prima di v è minore e ogni valore dopo è maggiore, quindi la regola vale per v e allo stesso modo per ogni nodo.
Il secondo esempio legge 5, 10, 6, 15, 20: il calo da 10 a 6 rivela il nodo nella posizione sbagliata. Ogni nodo viene visitato una volta: tempo O(n) e spazio O(n) per la lista.
Algoritmo
- Scrivi
walk(i): se la posizione è vuota, fermati; altrimenti visita2*i+1, aggiungitree[i], poi visita2*i+2. - Chiama
walk(0)per raccogliere i valori in ordine. - Per ogni posizione
ka partire da1, sevalues[k-1] ≥ values[k], restituiscifalse. - Restituisci
true.
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 TrueTrasporta l'intervallo consentito lungo l'albero
Intuizione
Ogni antenato impone un limite a un nodo: sotto a se il nodo si trova nel sottoalbero sinistro di un antenato che contiene a, sopra a se si trova nel sottoalbero destro. Insieme, i limiti formano un intervallo aperto (low, high), e il nodo si trova nella posizione corretta esattamente quando il suo valore è strettamente compreso al suo interno.
Costruisci l’intervallo man mano che scendi. Un figlio sinistro mantiene low e riceve high = v; un figlio destro mantiene high e riceve low = v. Nel secondo esempio, 15 passa (10, 15) al figlio sinistro, e 6 non supera subito il controllo. I valori sono compresi tra 0 e 10^5, quindi -1 e 100001 fungono da assenza di limite. Ogni nodo viene controllato una volta: tempo O(n), con O(h) nodi sullo stack.
Algoritmo
- Inserisci
(0, -1, 100001): la radice, senza limiti effettivi. - Estrai
(i, low, high). Setree[i]non è strettamente compreso tralowehigh, restituiscifalse. - Inserisci ogni figlio effettivo: quello sinistro in
2*i+1con(low, tree[i]), quello destro in2*i+2con(tree[i], high). - Quando lo stack è vuoto, restituisci
true.
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
Trappole e casi limite
- Confrontare un nodo solo con i suoi figli. In
[10, 5, 15, -1, -1, 6, 20]ogni coppia genitore-figlio sembra corretta, eppure il6viola il limite della radice. - Consentire valori uguali.
[12, 7, 12]non è valido: confronta con<, mai con≤. - Usare
0come limite inferiore «nessun limite». Questo rifiuta l’albero valido[0]. - Leggere un figlio senza verificare
2*i+1 < tree.length. In[12, 7, 12], l’indice3supera la fine. - In Lua e R, gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 per
2*i+1e leggitree[i + 1].
Domande frequenti3
Qual è la complessità temporale della convalida di un albero di ricerca binario?
Il controllo in ordine e il controllo dell'intervallo visitano ogni nodo una sola volta: tempo O(n), con spazio aggiuntivo O(h) per lo stack del controllo dell'intervallo, su un albero di profondità h. Confrontare ogni nodo con i suoi interi sottoalberi costa O(n × h), che arriva a O(n²) in un albero a forma di percorso.
Riesci a convalidare un BST con una visita in ordine senza memorizzare ogni valore?
Sì. Il controllo confronta ogni valore solo con quello precedente, quindi conserva il valore precedente in una variabile invece che in una lista e restituisci false non appena un valore non è maggiore. Lo spazio aggiuntivo scende a O(h) per la ricorsione o lo stack.
Un albero di ricerca binario può contenere valori duplicati?
Non secondo la definizione rigorosa usata qui: un valore uguale non rientra in nessuno dei due lati. Alcuni manuali consentono valori uguali da un lato, per esempio a destra. Secondo questa regola, un confronto rigoroso diventa ≤.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isValidBST(tree):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
tree = [8, 3, 12, 1, 6, 10, 15]
Output atteso
true