Binary Tree Zigzag Level Order Traversal
Ricevi un albero binario memorizzato nell’array root. La radice si trova all’indice 0, i figli dell’indice i si trovano in 2*i+1 (sinistra) e 2*i+2 (destra), -1 indica una posizione vuota e l’array può terminare con ulteriori voci -1.
Restituisci i valori dei nodi livello per livello in ordine zigzag: il livello della radice da sinistra a destra, quello successivo da destra a sinistra e così via, alternando fino al livello più profondo. Questa visita è anche chiamata visita per livelli a spirale.
Funzione
- rootinteger-array
- l'albero in ordine di heap, con -1 per una posizione vuota
- Restituisceinteger-2d-array
- un elenco di valori per livello, prima il livello superiore, alternando da sinistra a destra e da destra a sinistra
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 voci
-1aggiuntive dopo l'ultimo nodo. - Entrambi i figli di una posizione vuota sono vuoti anch’essi e l’albero ha al massimo
14livelli.
Esempi
- Input
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Output
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Spiegazione
- Leggendo da sinistra a destra, i livelli sono
8;12, 5;1, 9, 14;4, 2, 11. I livelli 1 e 3 procedono all’indietro:[5, 12]e[11, 2, 4].
- Input
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Output
- [[1], [3, 2], [4, 5, 6, 7]]
- Spiegazione
- Un albero completo di tre livelli: il livello centrale si inverte in
[3, 2]e il terzo procede di nuovo da sinistra a destra. Le due voci finali-1sono le posizioni dei figli vuote di4.
- Input
- root = [5]
- Output
- [[5]]
- Spiegazione
- Un singolo nodo è un livello di un valore, letto in entrambe le direzioni.
Per approfondire
Riesci a mettere ogni valore direttamente nella sua posizione finale nella propria riga, senza invertire nulla e senza usare una seconda pila?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Raccogli prima i livelli, ciascuno da sinistra a destra, come in una semplice visita in ordine per livelli. Quali di queste liste devono cambiare e in che modo?
Numera i livelli partendo da 0 alla radice. I livelli dispari si leggono al contrario. Invertire una lista costa quanto leggerla, quindi invertire quei livelli mantiene l'intera operazione lineare.
Per saltare l’inversione, mantieni il livello corrente in uno stack e inserisci i nodi figli in un secondo stack mentre estrai: prima il figlio sinistro quando leggi da sinistra a destra, prima il figlio destro quando leggi da destra a sinistra. Il secondo stack estrae quindi il livello successivo nell’ordine necessario.
Soluzione
I livelli derivano da una normale ricerca in ampiezza. La novità è la direzione: ogni altro livello viene invertito. Inverti le righe dispari dopo averle create oppure conserva ogni livello in una pila, che restituisce gli elementi nell’ordine opposto a quello in cui sono stati inseriti.
Ordine dei livelli, poi inverti un livello sì e uno no
Intuizione
Una coda che elabora un livello per round restituisce ogni livello da sinistra a destra. Numera i livelli a partire da 0 alla radice: il percorso a zigzag legge i livelli dispari da destra a sinistra, quindi invertire esattamente quelle righe dà la risposta.
La ricerca visita ogni nodo una volta e ogni inversione tocca ogni valore un'altra volta, quindi il tempo è O(n).
Algoritmo
- Avvia una coda con l’indice
0. - Per ogni iterazione, salva la lunghezza della coda
s, rimuovi dalla codasindici inserendoli in una nuova riga e accoda i figli esistenti di ciascuno, prima quello sinistro e poi quello destro. - Se la risposta contiene già un numero dispari di righe, inverti la riga.
- Aggiungi la riga e continua finché la coda non è vuota.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsDue pile
Intuizione
Mantieni il livello corrente in uno stack che estrae gli elementi nella direzione in cui viene letto il livello e inserisci i figli di ciascun nodo estratto in un secondo stack. Quando lo stack corrente si svuota, il secondo contiene il livello successivo.
L'ordine di inserimento è ciò che lo fa funzionare. Estraendo da sinistra a destra, inserisci il figlio sinistro di ciascun nodo, poi quello destro: il figlio destro del nodo più a destra viene inserito per ultimo, quindi il livello successivo viene estratto dalla sua estremità destra. Estraendo da destra a sinistra, inserisci prima il figlio destro, poi quello sinistro, e il figlio sinistro del nodo più a sinistra viene inserito per ultimo.
Esempio 1: estrai 8, inserisci 12, 5. Estrai 5, 12, poi inserisci 14 da 5 e 9, 1 da 12. Estrai 1, 9, 14, poi inserisci 4, 2 da 9 e 11 da 14. Estrai 11, 2, 4.
Ogni nodo viene inserito ed estratto una volta: tempo O(n), senza un passaggio di inversione.
Algoritmo
- Aggiungi l'indice
0della radice a uno stack e inizia a leggere da sinistra a destra. - Finché lo stack non è vuoto, estrai ogni indice in una nuova riga e aggiungi ciascun figlio esistente del nodo estratto a un secondo stack: prima il sinistro e poi il destro quando leggi da sinistra a destra, prima il destro e poi il sinistro altrimenti.
- Aggiungi la riga alla risposta.
- Imposta il secondo stack come quello corrente, inverti la direzione e ripeti.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Trappole e casi limite
- Invertire l'ordine in cui i figli entrano in una singola coda. I fratelli si scambiano di posto, ma i genitori mantengono il loro ordine: il terzo livello dell'esempio 1 risulta
[9, 1, 14]. - Contare i livelli a partire da 1. Ogni inversione sposta tutto di un livello e l'esempio 1 restituisce
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]. - Usare lo stesso ordine di inserimento a ogni livello nella versione con due pile. Il terzo livello dell'esempio 1 viene quindi estratto come
[9, 1, 14]. - Inserire i figli nella pila da cui stai ancora estraendo. Vengono estratti prima del resto del livello del genitore.
- Ordinare una riga invece di invertirla. L'ultimo livello dell'esempio 1 deve essere
[11, 2, 4], risultato che nessun ordinamento produce.
Domande frequenti3
Qual è la differenza tra la visita zigzag e la visita per livelli?
Visitano gli stessi livelli con gli stessi nodi. L’ordine per livello legge ogni livello da sinistra a destra; l’ordine a zigzag legge un livello ogni due da destra a sinistra, iniziando dal livello sotto la radice. Entrambi hanno complessità temporale O(n).
La visita a zigzag è la stessa cosa della visita a spirale di un albero?
Sì, i due nomi descrivono lo stesso percorso. Alcuni testi iniziano il secondo livello da sinistra invece che da destra, spostando le inversioni di un solo livello. Qui il livello della radice procede da sinistra a destra e quello successivo da destra a sinistra.
Si può eseguire l'attraversamento per livelli a zigzag con una deque?
Sì. Mantieni ogni livello nella deque nell’ordine da sinistra a destra. In un livello da sinistra a destra, preleva i nodi dall’inizio e aggiungi i loro figli, prima quello sinistro e poi quello destro, alla fine. In un livello da destra a sinistra, preleva i nodi dalla fine e aggiungi i loro figli, prima quello destro e poi quello sinistro, all’inizio. Il numero di nodi prelevati all’inizio di un turno continua a indicare il livello.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def zigzagLevelOrder(root):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Output atteso
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]