Diameter 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 (a sinistra) e 2*i+2 (a destra), -1 indica una posizione vuota e l’array può terminare con ulteriori voci -1. Restituisci il diametro dell’albero: il numero di archi nel percorso più lungo tra due nodi qualsiasi. Il percorso può passare per la radice oppure rimanere all’interno di un sottoalbero.
Funzione
- treeinteger-array
- l'albero binario in ordine per livelli, con -1 per una posizione vuota
- Restituisceinteger
- il numero di archi del percorso più lungo tra due nodi
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 voci
-1aggiuntive dopo l'ultimo nodo. - Entrambi i figli di uno spazio vuoto sono vuoti a loro volta, e la profondità è al massimo
14.
Esempi
- Input
- tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
- Output
- 4
- Spiegazione
- Il percorso
7,4,3,8,6(indici9,4,1,0,2) contiene cinque nodi collegati da quattro archi. Svolta alla radice: tre archi scendono lungo il lato sinistro e uno lungo quello destro.
- Input
- tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
- Output
- 4
- Spiegazione
- Il percorso
3,1,5,9,4ha quattro archi e svolta in corrispondenza di5all’indice1. La radice non ha un figlio destro, quindi un percorso che passa per la radice comprende solo i tre archi lungo il lato sinistro.
- Input
- tree = [6, -1, -1]
- Output
- 0
- Spiegazione
- Un singolo nodo non ha archi. Il percorso più lungo è il nodo stesso, di lunghezza
0.
+12 test nascosti all’invio
Per approfondire
Come restituiresti il percorso stesso, ovvero i valori dei nodi da un'estremità all'altra del diametro?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Ogni percorso in un albero ha un nodo più alto, in cui passa dalla salita alla discesa. Se conoscessi quel nodo, quanto potrebbe essere lungo il percorso che lo attraversa?
Un percorso che svolta nel nodo
iscende nel sottoalbero sinistro e in quello destro. Al massimo è l'altezza del figlio sinistro più l'altezza del figlio destro, dove un'altezza conta i nodi del percorso discendente più lungo e una posizione vuota ha altezza0.Calcola le altezze dal basso verso l’alto in un’unica visita in postordine: l’altezza di un nodo è
1 + max(left, right). Mentre hailefterightin un nodo, aggiorna la risposta conleft + right.
Soluzione
Il percorso più lungo non deve necessariamente passare per la radice, quindi misurare i due lati della radice non basta. Ogni percorso ha un nodo più alto, in cui passa dalla salita alla discesa, e il percorso più lungo che cambia direzione in un nodo è la sua altezza sinistra più la sua altezza destra. Un'unica visita in post-ordine calcola ogni altezza dal basso verso l'alto e controlla ogni punto di svolta lungo il percorso, in O(n).
Misura ogni coppia di nodi
Corretto, ma non termina sui test più grandi
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, quindi il suo genitore si trova all’indice (i-1)/2, arrotondato per difetto. Una posizione è reale solo se il suo indice è all’interno dell’array e il valore in quella posizione non è -1. In [8, 3, 6, 1, 4, -1, -1, -1, -1, 7], il 7 all’indice 9 ha il genitore all’indice 4, e quel 4 ha il genitore all’indice 1.
Il diametro è la distanza massima tra due nodi, quindi puoi misurare ogni coppia. Per ottenere la distanza tra gli indici a e b, risali verso la radice un passo alla volta finché non si incontrano, partendo sempre dall’indice più grande. Un indice più grande non si trova mai a un livello più alto, quindi quel passo non supera mai il punto d’incontro. Il numero di passi è il numero di archi. Per 9 e 2: il 9 risale fino a 4 e poi fino a 1, il 2 risale fino a 0 e l’1 risale fino a 0. Quattro passi.
È corretto, ma lento. Il test più grande è un albero completo di 16383 nodi, che genera circa 1.3 × 10^8 coppie, e ogni coppia richiede fino a 26 passi. Miliardi di passi per una sola risposta sono ben oltre il limite di tempo.
Algoritmo
- Raccogli gli indici di tutti i nodi reali.
- Per ogni coppia
(a, b), impostaedges = 0e ripeti finchéa == b: sostituisci l'indice più grande con il suo genitore e aggiungi1aedges. - Conserva il valore più grande di
edgesche trovi e restituiscilo.
def diameterOfBinaryTree(tree):
nodes = [i for i, value in enumerate(tree) if value != -1]
best = 0
for x in range(len(nodes)):
for y in range(x + 1, len(nodes)):
a, b = nodes[x], nodes[y]
edges = 0
while a != b:
# A larger index is never higher up, so climb from it.
if a > b:
a = (a - 1) // 2
else:
b = (b - 1) // 2
edges += 1
best = max(best, edges)
return bestMisura entrambe le altezze in ogni nodo
Intuizione
Guarda il percorso più lungo dal suo nodo più alto, quello in cui smette di salire e inizia a scendere. Da lì scende il più possibile lungo il lato sinistro e il più possibile lungo il lato destro. Sia height(c) il numero di nodi nel percorso discendente più lungo a partire da c, con 0 per una posizione vuota. Quindi, il percorso più lungo che svolta nel nodo i ha height(2*i+1) + height(2*i+2) archi, uno per ciascuno di quei nodi.
Prova quindi ogni nodo come punto di svolta e conserva il risultato migliore. Nel secondo esempio, il 5 all'indice 1 ha altezza 2 a sinistra (1, 3) e 2 a destra (9, 4), per un percorso di quattro archi. La radice ha altezza 3 a sinistra e 0 a destra, per un totale di soli tre.
Ogni chiamata a height visita un intero sottoalbero e un nodo viene visitato di nuovo per ogni suo antenato, quindi il costo è O(n·h). Con h ≤ 14 è abbastanza veloce in questo caso, ma in un albero di puntatori a forma di catena h può arrivare a n e la stessa idea costa O(n²). Le chiamate ripetute a height sono lo spreco che l'approccio successivo elimina.
Algoritmo
- Scrivi
height(i):0per una posizione vuota, altrimenti1 + max(height(2*i+1), height(2*i+2)). - Per ogni nodo reale
i, calcolaheight(2*i+1) + height(2*i+2). - Restituisci la somma più grande.
def diameterOfBinaryTree(tree):
n = len(tree)
def height(i):
# Nodes on the longest downward path from i; an empty spot has 0.
if i >= n or tree[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
best = 0
for i in range(n):
if tree[i] != -1:
# The longest path that turns at node i goes down both sides.
best = max(best, height(2 * i + 1) + height(2 * i + 2))
return bestUn passaggio postordine sulle altezze
Intuizione
L’altezza di un nodo dipende solo dalle altezze dei suoi due figli, e sono gli stessi due numeri necessari per verificare il punto di svolta. Quindi calcolali una sola volta, dal basso verso l’alto. Una visita post-ordine completa entrambi i figli prima del loro genitore. A ogni nodo hai quindi left e right: aggiorna la risposta con left + right e passa 1 + max(left, right) al genitore.
Nel primo esempio la foglia 7 restituisce 1, il 4 sopra di essa restituisce 2 e il 3 restituisce 3, perché l’altro figlio, 1, ha altezza 1. Il 6 restituisce 1. Alla radice left + right = 3 + 1 = 4, la risposta. Il valore migliore offerto da qualsiasi altro nodo è 3, con 1 + 2 = 3.
Ogni nodo viene visitato una volta, quindi il tempo è O(n), e la ricorsione è profonda quanto l’albero, O(h), circa un frame per livello. La risposta viene mantenuta in una variabile esterna alla ricorsione, perché ciò che restituisce una chiamata (un’altezza) non è ciò che vuoi alla fine (la lunghezza di un percorso).
Algoritmo
- Imposta
best = 0e scriviheight(i). Per una posizione vuota, restituisci0. - Calcola
left = height(2*i+1)eright = height(2*i+2). - Imposta
bestal maggiore trabesteleft + right. - Restituisci
1 + max(left, right). - Chiama
height(0)e restituiscibest.
def diameterOfBinaryTree(tree):
n = len(tree)
best = 0
def height(i):
# Returns the height of node i and updates best on the way back up.
nonlocal best
if i >= n or tree[i] == -1:
return 0
left = height(2 * i + 1)
right = height(2 * i + 2)
best = max(best, left + right) # the longest path that turns at node i
return 1 + max(left, right)
height(0)
return best
Trappole e casi limite
La maggior parte delle risposte errate conta la cosa sbagliata o misura nel nodo sbagliato.
- Contare i nodi invece degli archi. Il percorso
7,4,3,8,6ha cinque nodi e lunghezza4, e un singolo nodo ha diametro0. - Misurare solo passando per la radice. Nel secondo esempio, il percorso migliore che passa per la radice ha tre archi e la risposta è quattro, con svolta all'indice
1. - Restituire il diametro dalla chiamata ricorsiva. Il nodo genitore ha bisogno delle altezze dei figli per costruire percorsi più lunghi; il diametro deve stare in una variabile separata.
- Mescolare due convenzioni per l'altezza. Se le altezze contano i nodi e per una posizione vuota si usa
0,left + rightdà già il numero di archi. Se le altezze contano gli archi, per una posizione vuota serve-1e la formula èleft + right + 2. Usare metà di una convenzione e metà dell'altra porta a un errore di uno o due. - Leggere oltre la fine. Una foglia vicina alla fine dell'array può avere indici dei figli oltre l'ultima voce. Considera vuota una posizione con indice oltre la fine.
- 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 del diametro di un albero binario?
La soluzione in postordine visita ogni nodo una sola volta, quindi richiede O(n) tempo e O(h) spazio aggiuntivo per la ricorsione, dove h è l’altezza. Calcolare le altezze separatamente in ogni nodo costa O(n·h), che diventa O(n²) in un albero a forma di catena.
Il diametro di un albero binario passa sempre per la radice?
No. Il percorso più lungo può trovarsi interamente all'interno di un sottoalbero, ad esempio quando la radice ha un ramo corto e un sottoalbero profondo e ramificato dall'altro lato. Ecco perché controlli left + right in ogni nodo, non solo nella radice.
Il diametro si conta in nodi o in archi?
Qui si conta in archi, i collegamenti tra nodi consecutivi nel percorso, quindi un singolo nodo ha diametro 0 e due nodi collegati hanno diametro 1. Alcuni libri contano invece i nodi, ottenendo un valore in più. Controlla quale dei due chiede il problema prima di aggiungere o sottrarre 1.
Come si trova il diametro di un albero binario senza ricorsione?
Visita i nodi in un ordine in cui ogni figlio venga prima del suo genitore. Un modo: inserisci la radice in una pila, estrai i nodi e aggiungili a una lista mentre inserisci i loro figli, poi percorri la lista all'indietro. Memorizza l'altezza di ogni nodo in un array, leggi le altezze dei due figli in ogni nodo e aggiorna la risposta con la loro somma. La complessità temporale resta O(n).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def diameterOfBinaryTree(tree):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Atteso
4