Convalidare un BST e le proprietà in-order
Convalidi un albero binario come BST usando limiti min/max propagati lungo l'albero e verificando che il percorso in-order produca una sequenza ordinata
Convalidare un BST e le proprietà in-order è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il problema della validazione di un BST
Validate BST (LeetCode #98) è un classico problema da colloquio che mette in difficoltà molti candidati. L'approccio ingenuo verifica soltanto che il valore di ogni nodo sia maggiore di quello del figlio sinistro e minore di quello del figlio destro, ma questo controllo locale non è sufficiente. Un nodo di un sottoalbero potrebbe rispettare la regola locale e tuttavia violare la proprietà globale del BST. La soluzione corretta propaga lungo l'albero limiti minimo e massimo validi.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')Approccio dei limiti minimo/massimo
Passi i limiti inferiore e superiore lungo la ricorsione. A ogni nodo, verifichi che low < node.val < high. Quando ricorre a sinistra, aggiorni il limite superiore a node.val (il sottoalbero sinistro deve contenere valori minori). Quando ricorre a destra, aggiorni il limite inferiore a node.val (il sottoalbero destro deve contenere valori maggiori). Inizi con low = -infinity e high = +infinity.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)Validazione tramite attraversamento in-order
Un approccio alternativo alla validazione sfrutta la proprietà di ordinamento in-order del BST: raccolga la sequenza in-order e verifichi che sia strettamente crescente. È una soluzione elegante e facile da comprendere. Tuttavia, usa O(n) di spazio aggiuntivo per memorizzare la sequenza. Una versione ottimizzata usa un singolo puntatore prev durante l'attraversamento, così da verificare ogni coppia senza memorizzare l'intera sequenza.
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # FalseConfronto dei due approcci di validazione
L'approccio dei limiti minimo/massimo ha complessità O(n) in tempo e O(h) in spazio, considerando soltanto i limiti nello stack delle chiamate. Anche l'approccio in-order con puntatore prev ha complessità O(n) in tempo e O(h) in spazio. Entrambi sono ottimali. L'approccio dei limiti minimo/massimo è più generale e si estende facilmente a problemi con vincoli aggiuntivi. Nei colloqui, si prepari a presentarli entrambi e a discutere i compromessi: dimostrare di conoscere le alternative è un segnale molto positivo.
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')Ripristino del BST: due nodi scambiati
Recover BST (LeetCode #99) ripristina un BST in cui sono stati scambiati esattamente due nodi. Durante l'attraversamento in-order, un BST correttamente ordinato produce una sequenza ordinata. Se due nodi sono stati scambiati, si verificano una o due violazioni in corrispondenza delle quali prev.val > current.val. Il primo nodo della prima violazione e il secondo nodo dell'ultima violazione sono i due nodi fuori posto: ne scambi i valori.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)Da BST a array ordinato tramite in-order
Convertire un BST in un array ordinato è immediato: esegua un attraversamento in-order e raccolga i valori. Questa operazione, con complessità O(n) in tempo e O(n) in spazio, è un modo rapido per applicare gli algoritmi sugli array ordinati, come la ricerca binaria e i due puntatori, ai dati di un BST. Spesso rappresenta un passaggio intermedio in problemi sui BST composti da più parti, come «unire due BST» o «trovare la mediana di un BST».
def bst_to_sorted_array(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]Unione di due BST
Per unire due BST in un unico array ordinato, converta ciascuno in un array ordinato in O(n) e O(m), quindi fonda i due array ordinati usando il passaggio di fusione del merge sort in O(n+m). Tempo totale: O(n+m). Se il risultato deve essere un BST bilanciato, passi l'array ordinato risultante all'algoritmo di conversione da array ordinato a BST. Scomporre il problema in sottoproblemi semplici è il segno distintivo di una soluzione chiara e facile da seguire durante un colloquio.
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]Conteggio dei nodi nell'intervallo di un BST
Conti quanti nodi hanno valori nell'intervallo [low, high]. Una scansione in-order a forza bruta ha complessità O(n). La versione che sfrutta il BST elimina rami inutili: se il valore del nodo corrente è minore di low, non serve controllare il sottoalbero sinistro, poiché anche tutti i suoi valori sono minori di low. Analogamente, elimini il sottoalbero destro quando il valore corrente è maggiore di high. Nel caso medio, la complessità è O(log n + k), dove k è il numero di nodi corrispondenti.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7 + 10 + 15 = 32Valori duplicati e BST con disuguaglianze strette o non strette
L'invariante standard di un BST usa una disuguaglianza stretta: i valori del sottoalbero sinistro sono strettamente minori e quelli del sottoalbero destro sono strettamente maggiori. Alcuni problemi consentono valori duplicati, collocandoli nel sottoalbero sinistro (left <= root) o in quello destro (root < right). Quando valida un BST, controlli sempre la definizione indicata dal testo del problema. L'approccio dei limiti minimo/massimo gestisce entrambe le varianti modificando il controllo del limite, che può essere stretto o inclusivo.
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')L'attraversamento in-order come strumento universale per i BST
L'attraversamento in-order è il coltellino svizzero dei problemi sui BST. Ogni volta che un problema su un BST riguarda l'ordine crescente, il k-esimo elemento, le query su intervalli o le proprietà di una sequenza, consideri se una scansione in-order, o il suo inverso, può fornire la risposta. La maggior parte dei problemi specifici dei BST si riduce a questo: attraversare in ordine crescente e fare qualcosa a ogni passaggio. Riconoscere rapidamente questa corrispondenza è una competenza fondamentale nei colloqui.
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')Valore più vicino in un BST
Trovi il nodo il cui valore è più vicino a un determinato target. Sfrutti l'ordinamento del BST: parta dalla radice, tenga traccia del valore più vicino trovato finora e si sposti verso il target, andando a sinistra se il target è minore e a destra se è maggiore. Questo approccio, con complessità O(h), è più efficiente di una scansione in-order e dimostra come usare efficacemente la proprietà del BST per ridurre lo spazio di ricerca.
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: la validazione dei BST con i limiti minimo/massimo, evitando il problema del controllo locale, l'alternativa del puntatore prev durante l'in-order per la validazione e l'uso dell'in-order come strumento universale dei BST per somme su intervalli, ricerca del valore più vicino e operazioni di fusione. Il prossimo argomento riguarda l'uso delle proprietà dell'in-order dei BST per trovare il k-esimo elemento più piccolo.
Domande Frequenti
La lezione «Convalidare un BST e le proprietà in-order» è gratuita?
Sì — il testo completo di «Convalidare un BST e le proprietà in-order» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Convalidare un BST e le proprietà in-order»?
Convalidi un albero binario come BST usando limiti min/max propagati lungo l'albero e verificando che il percorso in-order produca una sequenza ordinata Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Convalidare un BST e le proprietà in-order»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Inserimento e ricerca in un BST
- Eliminazione da un BST: tre casi
- Convalidare un BST e le proprietà in-order
- K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato