Binary Tree Right Side View
L'array root contiene un albero binario. La radice si trova all'indice 0, i figli del nodo all'indice i si trovano agli indici 2*i+1 (sinistra) e 2*i+2 (destra), -1 indica una posizione vuota e possono esserci ulteriori valori -1 alla fine.
Osserva l'albero dal lato destro. Ogni livello mostra esattamente un nodo, quello più a destra, e nasconde gli altri. Elenca quei valori dal livello della radice fino al livello più profondo.
Funzione
- rootinteger-array
- l'albero in ordine di heap, con -1 per una posizione vuota
- Restituisceinteger-array
- il valore più a destra di ogni livello, partendo dal livello superiore
Vincoli
1 ≤ root.length ≤ 32767- Ogni
root[i]è-1oppure un valore con0 ≤ root[i] ≤ 104. - I valori dei nodi sono distinti.
root[0]non è mai-1, quindi l'albero ha almeno un nodo.- L'array può terminare con ulteriori voci
-1dopo l'ultimo nodo. - Entrambi i figli di uno spazio vuoto sono vuoti e l’albero ha al massimo
14livelli.
Esempi
- Input
- root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
- Output
- [5, 9, 1, 3]
- Spiegazione
- Da destra vedi
5,9e1(indice 6). Il quarto livello contiene solo3, all'indice 8 sotto7nel sottoalbero sinistro. Nulla sul lato destro arriva così in profondità, quindi3è visibile.
- Input
- root = [6, 0, -1, 8, -1, -1, -1]
- Output
- [6, 0, 8]
- Spiegazione
- L’albero è una catena di figli sinistri:
6,0,8. Ogni livello contiene un nodo, quindi li vedi tutti e tre, anche se nessuno di essi è un figlio destro.
- Input
- root = [42]
- Output
- [42]
- Spiegazione
- Un array di lunghezza 1: la radice
42non ha alcuna posizione figlia e la vista è quel singolo valore.
Per approfondire
Come otterresti la vista del lato destro di un albero in cui ogni nodo può avere un numero qualsiasi di figli, memorizzati in un elenco da sinistra a destra?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scendendo lungo i figli destri dell'esempio 1 si ottiene
5, 9, 1e ci si ferma. La risposta ha un quarto valore. Da dove viene?Raggruppa i nodi per profondità invece che per lato. Scrivi ogni livello da sinistra a destra: in quale punto di quell’elenco si trova il nodo che vedrebbe una persona a destra?
Mantieni una lista
view. Visita l’albero in profondità, tenendo traccia della profondità, prima il figlio destro e poi quello sinistro, e aggiungi un nodo quando la sua profondità è uguale alla lunghezza diview. Funziona anche una visita con una coda, un livello per turno: aggiungi l’ultimo nodo di ogni turno.
Soluzione
Vedi il nodo più a destra di ogni livello, e non è detto che sia un figlio destro: l'ultimo valore dell'esempio 1 si trova nel sottoalbero sinistro. Una ricerca in ampiezza fa sì che quel nodo sia l'ultimo di ogni turno; una visita in profondità che procede prima a destra lo incontra prima di qualsiasi altro nodo del suo livello.
Breadth-first, ultimo nodo di ogni livello
Intuizione
Elabora l’albero un livello per ogni turno. Quando inizia un turno, la coda contiene esattamente un livello da sinistra a destra, quindi l’ultimo indice che estrai dalla coda nel turno corrisponde al nodo più a destra di quel livello e il suo valore viene inserito nella risposta.
Nell’esempio 1 i turni sono [5], [2, 9], [7, 4, 1] e [3], e le loro ultime voci danno 5, 9, 1, 3. A decidere è il livello, non il lato: 3 si trova nel sottoalbero sinistro, ma è da solo al suo livello.
Ogni indice viene inserito ed estratto dalla coda una volta, quindi il tempo è O(n). La coda cresce fino alla larghezza del livello più ampio, O(n) nel caso peggiore.
Algoritmo
- Accoda l'indice
0della radice. - Inizia un turno salvando la lunghezza della coda
s. - Rimuovi dalla coda
sindici. Per ogni indicei, accoda2i+1e poi2i+2se sono minori della lunghezza dell'array e diversi da-1. - Aggiungi il valore dell'ultimo indice rimosso dalla coda nel turno.
- Ripeti finché la coda non è vuota, poi restituisci la risposta.
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return viewPrima in profondità, figlio destro per primo
Intuizione
Procedi in profondità, provando il figlio destro prima di quello sinistro, e tieni traccia della profondità, 0 alla radice. La prima volta che la visita raggiunge la profondità d, la risposta contiene esattamente d valori. Aggiungi allora il valore del nodo e ignora tutti i nodi successivi a quel livello.
Quel primo nodo è quello più a destra: ogni volta che due percorsi verso un livello si separano, la visita segue il ramo destro fino in fondo prima di tornare indietro e imboccare quello sinistro. Nell'esempio 1 la visita raggiunge 5, 9, 1, 2, 4, 7, 3: salta 2, 4 e 7, i cui livelli hanno già un valore, e aggiunge 3.
Ogni nodo viene visitato una volta, tempo O(n), con una chiamata per livello nello stack, al massimo 14.
Algoritmo
- Inizia con una risposta vuota e la radice a profondità 0.
- Salta un indice che supera la fine dell'array o contiene
-1. - Quando la lunghezza della risposta è uguale alla profondità, aggiungi il valore: il percorso ha raggiunto un nuovo livello, arrivandoci da destra.
- Ricorri prima nel figlio destro
2i+2, poi in quello sinistro2i+1, ciascuno a un livello di profondità in più. - Restituisci la risposta.
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
Trappole e casi limite
- Seguire solo i figli destri a partire dalla radice. L'esempio 1 restituisce quindi
[5, 9, 1]e non include3; l'esempio 2 restituisce[6]. - Leggere l'ultimo slot di ogni livello,
root[2^(d+1)-2]. Nell'esempio 2 l'indice 6 contiene-1; il nodo visibile è8all'indice 3. - Saltare il controllo della lunghezza in corrispondenza di una posizione figlia. Nell'esempio 1,
3è l'ultimo elemento, quindi le sue posizioni figlie 17 e 18 non esistono. - Accodare prima il figlio destro, mantenendo il nodo finale di ogni iterazione. In questo modo si raccoglie la vista sinistra,
[5, 2, 7, 3]. - Permettere ai nodi successivi di sovrascrivere quelli precedenti nella visita da destra a sinistra, ottenendo così anche la vista sinistra.
Domande frequenti3
Qual è la complessità temporale e spaziale della vista del lato destro di un albero binario?
Il tempo è O(n) per n nodi e nessuna soluzione può saltare dei nodi, poiché il nodo più a destra di un livello può trovarsi in qualsiasi punto. Lo spazio è O(w) per la coda, dove w è il livello più ampio, oppure O(h) per la visita da destra a sinistra su un albero di h livelli.
Una ricerca in profondità che esplora prima a sinistra può risolverlo?
Sì, se sovrascrivi invece di mantenere il primo valore. Una visita da sinistra a destra incontra i nodi di ogni livello da sinistra a destra, quindi memorizza il valore di ogni nodo alla sua profondità e lascia che i nodi successivi sostituiscano quelli precedenti. Ogni profondità termina con il suo valore più a destra. È comunque O(n), ma scrive una volta per nodo.
Dovrei usare la ricerca in ampiezza o in profondità qui?
Entrambi sono lineari. La ricerca in ampiezza segue la definizione, un livello per iterazione. La ricerca in profondità mantiene solo il percorso corrente, risparmiando memoria in un albero ampio, e la sua forma ricorsiva è più breve di qualche riga.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def rightSideView(root):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Output atteso
[5, 9, 1, 3]