Maximum Depth of Binary Tree
Ti viene dato un albero binario memorizzato nell’array tree in ordine per livelli. La radice si trova all’indice 0, i figli del nodo all’indice i si trovano agli indici 2*i+1 (sinistro) e 2*i+2 (destro), -1 indica una posizione vuota e l’array può terminare con elementi -1 aggiuntivi. Restituisci la profondità massima dell’albero: il numero di nodi nel percorso più lungo dalla radice fino a una foglia.
Funzione
- treeinteger-array
- l'albero binario in ordine per livelli, con -1 per una posizione vuota
- Restituisceinteger
- il numero di nodi nel percorso più lungo dalla radice a una foglia
Vincoli
1 ≤ tree.length ≤ 32767- Ogni
tree[i]è-1oppure un valore con0 ≤ tree[i] ≤ 1000. tree[0]non è mai-1, quindi l'albero ha almeno un nodo.- L'array può terminare con elementi aggiuntivi
-1dopo l'ultimo nodo. - Entrambi i figli di una posizione vuota sono vuoti a loro volta e la profondità è al massimo
14.
Esempi
- Input
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Output
- 4
- Spiegazione
- Il percorso più lungo è
5,8,3,6(indici0,1,4,9), e contiene 4 nodi. Il percorso che passa per1si ferma dopo 2 nodi.
- Input
- tree = [7, -1, -1]
- Output
- 1
- Spiegazione
- Le due voci
-1sono le posizioni vuote dei figli della radice. La radice da sola è un percorso di un nodo, quindi la profondità è1, non0.
- Input
- tree = [2, -1, 9, -1, -1, -1, 4]
- Output
- 3
- Spiegazione
- La radice
2non ha un figlio sinistro. Il suo figlio destro9all'indice2ha4all'indice6come figlio destro: un percorso di 3 nodi.
+13 test nascosti all’invio
Per approfondire
Come restituiresti i valori di un percorso radice-foglia più lungo, non solo la sua lunghezza? Se più percorsi hanno la stessa lunghezza, quale restituiresti e come lo specificheresti nel contratto?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Pensa alla radice. Se conoscessi la profondità del suo sottoalbero sinistro e quella del suo sottoalbero destro, quale sarebbe la profondità dell’intero albero?
È
1per la radice più la maggiore delle profondità dei due sottoalberi, e un punto vuoto ha profondità0. La stessa regola vale per ogni nodo, quindi una visita che conosce la profondità di ogni nodo può trovare la risposta.Tieni uno stack di coppie, un indice del nodo e la sua profondità, iniziando dalla radice con profondità 1. Estrai una coppia, ricorda la profondità massima raggiunta e inserisci ogni figlio in
2*i+1e2*i+2che si trova all’interno dell’array e non è-1, con la profondità aumentata di uno.
Soluzione
La profondità è determinata dal ramo singolo più lungo e non puoi sapere quale sia senza esaminare ogni nodo. Quindi il compito consiste in una visita completa che tenga traccia della profondità raggiunta in ciascun nodo. La ricorsione, una ricerca in ampiezza livello per livello e una ricerca in profondità con uno stack personalizzato permettono tutte di farlo in un'unica passata; differiscono nel modo in cui tengono traccia della posizione corrente.
Ricorsione sui due sottoalberi
Intuizione
Per prima cosa, come spostarsi nell'array. Il nodo all'indice i ha il figlio sinistro all'indice 2*i+1 e il figlio destro all'indice 2*i+2. Un figlio esiste solo se il suo indice è all'interno dell'array e il valore in quella posizione non è -1. In [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], la radice 5 ha figli agli indici 1 e 2; il nodo 8 all'indice 1 ha uno spazio vuoto a sinistra all'indice 3 e il nodo 3 all'indice 4 alla sua destra; infine, il nodo 3 ha sotto di sé il nodo 6 all'indice 9.
Passiamo all'idea. Il percorso più profondo che passa per un nodo scende nel sottoalbero più profondo tra i suoi due. Quindi la profondità del sottoalbero all'indice i è 1 per il nodo stesso più la maggiore tra le profondità agli indici 2*i+1 e 2*i+2. Una posizione vuota ha profondità 0, che conclude la ricorsione. Una foglia ottiene 1 + max(0, 0) = 1 e i valori risalgono fino alla radice.
Ogni nodo viene visitato una volta, quindi il tempo è O(n). Lo stack delle chiamate contiene un frame per ogni livello del percorso corrente, O(h), dove h è la profondità, al massimo 14 in questo caso. È questo limite a rendere sicura la ricorsione in questo problema. In un albero basato su puntatori e strutturato come una lunga catena, lo stesso codice raggiungerebbe il limite di ricorsione, che in Python è di 1000 frame.
Algoritmo
- Scrivi
depth(i): seiè oltre la fine dell'array otree[i]è-1, restituisci0. - Altrimenti restituisci
1 + max(depth(2*i+1), depth(2*i+2)). - Restituisci
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Ricerca in ampiezza, livello per livello
Intuizione
La profondità massima è il numero di livelli dell'albero, quindi puoi contare i livelli invece di seguire i percorsi. Una coda visita i nodi in ordine di livello: inizializzala con la radice e, ogni volta che estrai un nodo, aggiungi i suoi figli effettivi in fondo.
Per contare i livelli, elabora la coda in gruppi. Prima di ogni gruppo, leggi quanti nodi contiene la coda. Sono esattamente i nodi di un livello, perché i figli che aggiungi durante il gruppo vengono inseriti dopo di essi. Estrai quel numero di nodi, inserisci i loro figli nella coda e aggiungi 1 alla profondità. Quando la coda è vuota, la profondità è il numero di gruppi. Nel primo esempio i gruppi sono [5], [8, 1], [3] e [6], quindi la risposta è 4.
Ogni nodo entra ed esce dalla coda una volta: tempo O(n). La coda contiene un livello alla volta: spazio O(w) per il livello più ampio w. In un albero completo, il livello inferiore contiene circa la metà dei nodi: 8192 dei 16383 a profondità 14.
Algoritmo
- Inserisci l’indice radice
0in una coda e impostadepth = 0. - Finché la coda non è vuota, aggiungi
1adepthe leggi la dimensione della coda. - Estrai quel numero di indici. Per ciascuno, accoda gli indici figli
2*i+1e2*i+2che si trovano all’interno dell’array e non sono-1. - Quando la coda è vuota, restituisci
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthRicerca in profondità con uno stack esplicito
Intuizione
Puoi seguire i percorsi, come fa la ricorsione, senza effettuare una singola chiamata ricorsiva. Tieni il tuo stack e memorizza ogni nodo insieme alla sua profondità, perché nient'altro ricorda quanto in profondità si trovi. Inizia con la coppia (0, 1): la radice, a profondità 1.
Estrai una coppia, confronta la sua profondità con la migliore vista finora e inserisci ogni figlio effettivo con depth + 1. Ogni nodo dell'albero viene inserito esattamente una volta, portando con sé la lunghezza del percorso che lo raggiunge, quindi la profondità massima tra quelle estratte è la risposta. Nel primo esempio, il 6 all'indice 9 viene inserito come (9, 4) e nessuna coppia va più in profondità.
Il tempo è O(n). Lo stack contiene i fratelli in attesa lungo il percorso corrente, al massimo circa uno per livello, quindi lo spazio è O(h), come con la ricorsione ma senza uno stack di chiamate che possa andare in overflow. Questa è la versione da usare quando un albero può essere profondo e si trasferisce senza modifiche agli alberi basati su puntatori.
Algoritmo
- Inserisci
(0, 1)in uno stack e impostabest = 0. - Estrai una coppia
(i, depth)e impostabestal maggiore trabestedepth. - Per ogni indice figlio
2*i+1e2*i+2che si trova all'interno dell'array e non è-1, inseriscilo condepth + 1. - Ripeti finché lo stack non è vuoto, quindi restituisci
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Trappole e casi limite
La maggior parte delle risposte sbagliate a questo problema presenta un errore di uno, oppure deriva dal trattare una posizione vuota come un nodo.
- Contare gli archi invece dei nodi. Qui un singolo nodo ha profondità
1; restituire0per esso, o3per un percorso di 4 nodi, significa contare uno in meno. - Saltare il controllo dei limiti. Una foglia vicina alla fine dell’array può avere indici dei figli oltre l’ultima posizione, perché l’array può terminare subito dopo l’ultimo nodo. Controlla
child < nprima di leggeretree[child]. - Ricavare la profondità dalla lunghezza dell’array. L’array può contenere voci
-1aggiuntive alla fine, quindi la sua lunghezza può corrispondere a un livello più profondo di quello di qualsiasi nodo reale. - Trattare
-1come un valore. Indica un nodo mancante, quindi non deve essere inserito nello stack, nella coda o conteggiato. - Dare per scontato che l’albero sia bilanciato. La risposta dipende dal ramo più lungo, come in una catena di 14 nodi a sinistra in cui ogni posizione a destra è vuota.
- Leggere la dimensione della coda all’interno del ciclo nella versione con visita in ampiezza. La dimensione cambia quando vengono aggiunti i figli, quindi salvala prima di iniziare il gruppo.
- Confondere l’offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 per il calcolo
2*i+1e leggitree[i + 1].
Domande frequenti4
Qual è la complessità temporale della profondità massima di un albero binario?
Ogni approccio visita ogni nodo una volta, quindi il tempo è O(n). Le versioni in profondità usano O(h) di spazio aggiuntivo per il percorso esplorato, dove h è la profondità. La versione in ampiezza usa O(w) per il livello più ampio, che può comprendere circa metà dei nodi di un albero completo.
Dovresti usare DFS o BFS per calcolare la profondità massima di un albero binario?
Entrambi forniscono la risposta corretta in tempo O(n). La ricerca in profondità è più breve da scrivere e usa una quantità di memoria proporzionale alla profondità, perciò è adatta agli alberi larghi e poco profondi. La ricerca in ampiezza conta direttamente i livelli e usa una quantità di memoria proporzionale al livello più ampio, perciò è adatta agli alberi profondi e stretti. Per trovare la profondità minima, la BFS è avvantaggiata, perché può fermarsi alla prima foglia che incontra.
Come si trova la profondità massima di un albero binario senza ricorsione?
Usa uno stack esplicito di coppie: un nodo e la sua profondità. Inizia con la radice alla profondità 1, estrai una coppia, registra la sua profondità e inserisci ogni figlio con una profondità aumentata di uno. La profondità massima estratta è la risposta. Funziona anche una coda elaborata un livello alla volta, contando uno per ogni livello.
Qual è la differenza tra la profondità e l'altezza di un albero binario?
La profondità di un nodo conta i passaggi dalla radice fino a esso, mentre l’altezza di un nodo conta i passaggi da esso fino alla sua foglia più profonda. La profondità massima dell’albero e l’altezza della radice sono lo stesso numero. Questo problema conta i nodi, quindi un singolo nodo ha profondità 1; alcuni libri contano invece gli archi, ottenendo un valore inferiore di uno.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def maxDepth(tree):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Atteso
4