Binary Tree Level Order Traversal

Q: Qual è la complessità temporale della visita in ordine di livello di un albero binario?

Sia la soluzione in ampiezza sia quella in profondità visitano ogni nodo una volta, quindi hanno una complessità temporale di O(n) per n nodi. La risposta stessa contiene n valori, quindi lo spazio è O(n) . Oltre a ciò, la coda contiene al massimo circa il livello più ampio e la ricorsione al massimo l’altezza dell’albero.

Q: Come fai a sapere dove termina un livello in una ricerca in ampiezza?

Leggi la dimensione della coda all’inizio di ogni round. In quel momento la coda contiene esattamente i nodi di un livello, quindi estrarne quel numero significa estrarre il livello e nient’altro. Funzionano anche altri due metodi: mantieni il livello corrente e quello successivo in due liste separate, oppure inserisci un marcatore dopo ogni livello.

Q: È possibile eseguire una visita in ordine di livello con la ricerca in profondità?

Sì. Passa a ogni nodo la sua profondità e aggiungi il suo valore alla lista corrispondente a quella profondità. Finché la visita percorre il sottoalbero sinistro prima di quello destro, ogni lista risulta ordinata da sinistra a destra. È anche O(n) ; la visita in ampiezza è più adatta perché produce i livelli in ordine.

Q: L'array è già memorizzato livello per livello. Perché non leggerlo a fette?

Per questo formato funziona: il livello d occupa gli indici da 2^d-1 a 2^(d+1)-2 , quindi puoi raccogliere i valori non vuoti di ogni intervallo e fermarti al primo intervallo senza valori. In un colloquio, però, l'albero è solitamente rappresentato da oggetti nodo con puntatori a sinistra e a destra, senza indici su cui suddividerlo. La visita basata su coda è quella che si applica anche a questa forma e a varianti come l'ordine a zigzag o la vista dal lato destro.

MedioVisita di alberi Coda

+10

Ti viene fornito un albero binario memorizzato nell'array tree. 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 ulteriori voci -1.

Restituisci i valori dei nodi livello per livello: un elenco contenente il valore della radice, poi un elenco con i valori del livello successivo, da sinistra a destra, e così via fino al livello più profondo.

Funzione

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-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, ciascuno da sinistra a destra

Vincoli

1 ≤ tree.length ≤ 32767
Ogni tree[i] è -1 oppure un valore con 0 ≤ tree[i] ≤ 1000.
tree[0] non è mai -1, quindi tree ha almeno un nodo.
L'array può terminare con voci -1 aggiuntive 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 = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Output: [[4], [9, 2], [6, 8, 5], [3]]
Spiegazione: La radice 4 ha come figli 9 e 2 agli indici 1 e 2. L'indice 3 è vuoto, quindi il terzo livello è 6 (indice 4, sotto 9), poi 8 e 5 (indici 5 e 6, sotto 2). Il 3 all'indice 9 è il figlio sinistro di 6, da solo al quarto livello.

Input: tree = [7, -1, -1]
Output: [[7]]
Spiegazione: Entrambi i figli della radice sono -1, quindi l'albero è il singolo nodo 7 e ha un livello.

Input: tree = [1, 3, -1, 5, -1, -1, -1]
Output: [[1], [3], [5]]
Spiegazione: Ogni nodo ha solo un figlio sinistro: 3 all’indice 1 e 5 all’indice 3. Ogni livello contiene un valore e le voci finali -1 non aggiungono nulla.

+15 test nascosti all’invio

Per approfondire

Puoi restituire i livelli in ordine a zigzag, il primo da sinistra a destra, il secondo da destra a sinistra e così via, senza ordinare alcun livello?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ogni livello deve risultare come un elenco a sé, ordinato da sinistra a destra. Una ricerca in ampiezza con una coda visita i nodi esattamente in quest'ordine. L'unica idea in più è capire dove finisce un livello: all'inizio di ogni iterazione, la coda contiene l'intero livello corrente e nient'altro, quindi la sua dimensione indica quanti nodi estrarre. Funziona anche una visita in profondità, purché tenga traccia della profondità di ogni nodo e proceda prima a sinistra e poi a destra.

In profondità, organizzato per profondità

Intuizione

Per prima cosa, vediamo come spostarci nell’array. Il figlio sinistro dell’indice i si trova in 2i+1 e quello destro in 2i+2. Un figlio manca quando il suo indice supera la fine dell’array o contiene -1. Nell’esempio 1, i figli di 9 (indice 1) si trovano agli indici 3 e 4, che contengono -1 e 6, quindi 9 ha solo un figlio destro.

Ora percorri l’albero in profondità e passa a ogni nodo la sua profondità, 0 per la radice. Mantieni una lista per ogni profondità. Quando raggiungi un nodo alla profondità d, aggiungi il suo valore alla lista d; se finora ci sono solo d liste, questo è il primo nodo di un nuovo livello, quindi prima crea una nuova lista.

Perché ogni livello risulta ordinato da sinistra a destra? Il percorso completa tutto il sottoalbero sinistro di un nodo prima di passare al sottoalbero destro. Considera due nodi allo stesso livello: nel punto in cui i loro percorsi dalla radice si dividono, uno va a sinistra e l’altro a destra, e il percorso raggiunge prima quello a sinistra. Nell’esempio 1, l’ordine è 4, 9, 6, 3, 2, 8, 5, che riempie le liste così: [4], [9, 2], [6, 8, 5], [3].

Ogni nodo viene visitato una volta, quindi il tempo richiesto è O(n) per n nodi, e le liste contengono n valori. La ricorsione raggiunge al massimo la profondità dell’albero, qui 15 livelli. La versione in R usa invece uno stack esplicito, inserendo prima il figlio destro e poi quello sinistro, così che il sinistro venga estratto per primo; infine raggruppa i valori in base alla profondità con split.

Algoritmo

Crea un elenco vuoto di livelli.
Visita la radice con profondità 0.
Al nodo i con profondità d, fermati se i supera la fine o se tree[i] è -1.
Se ci sono solo d elenchi, aggiungine uno vuoto. Aggiungi tree[i] all’elenco d.
Visita 2i+1, poi 2i+2, entrambi con profondità d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Prima in ampiezza, un livello per turno

Intuizione

Una coda restituisce i valori nello stesso ordine in cui sono entrati. Inserisci la radice. Poi estrai ripetutamente un nodo e inserisci i suoi figli, prima il figlio sinistro. Ogni nodo del livello d+1 entra nella coda quando il suo genitore al livello d ne esce, quindi tutti i nodi del livello d escono prima che ne esca uno qualsiasi del livello d+1 e, all'interno di un livello, i nodi escono da sinistra a destra.

In questo modo si ottiene un flusso di valori in ordine di livello. Per suddividerlo in livelli, leggi la dimensione della coda all'inizio di un turno. In quel momento la coda contiene esattamente il livello corrente: il livello precedente è stato rimosso e nessun nodo del livello successivo è ancora arrivato. Estrai quel numero di nodi e inseriscili in un'unica lista. I figli che aggiungono appartengono al turno successivo.

Nell'esempio 1 la coda inizia come [4]: estrai 1 nodo, riga [4], e entrano 9, 2. Estrai 2 nodi, riga [9, 2], ed entrano 6, 8, 5. Estrai 3 nodi, riga [6, 8, 5], ed entra 3. Estrai 1 nodo, riga [3], e la coda è vuota.

Ogni nodo entra ed esce dalla coda una sola volta, quindi il tempo è O(n). La coda contiene al massimo circa un livello, fino a 16384 nodi al livello più profondo di un albero completo di profondità 14. Usa una vera coda o un indice iniziale: in molti linguaggi, rimuovere il primo elemento da una semplice lista basata su array sposta tutti gli elementi successivi.

Algoritmo

Inserisci l’indice 0 della radice in una coda.
Finché la coda non è vuota, leggi la sua dimensione s e avvia una riga vuota.
Estrai s indici. Per ogni indice i, aggiungi tree[i] alla riga.
Aggiungi 2i+1, poi 2i+2, alla coda quando l’indice è all’interno dell’array e non contiene -1.
Aggiungi la riga alla risposta e avvia il turno successivo.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    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(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Trappole e casi limite

La visita stessa è breve. Gli errori si trovano nei confini dei livelli e negli spazi vuoti.

Leggere la dimensione della coda mentre la stai ancora svuotando. In un ciclo come while (j < queue.length) la lunghezza aumenta man mano che arrivano i figli, quindi il livello successivo finisce nella riga corrente. Leggi la dimensione una volta, prima che inizi il giro.
Aggiungere il figlio destro prima di quello sinistro. Ogni livello risulterà quindi da destra a sinistra. Lo stesso vale per una visita in profondità che visita prima il sottoalbero destro.
Trattare -1 come un valore. Uno spazio vuoto non è un nodo, quindi non entra mai in una riga né nella coda.
Dimenticare il controllo dei limiti. I figli dei nodi più profondi possono trovarsi oltre la fine dell'array, quindi verifica child < n prima di leggere tree[child].
Restituire livelli vuoti. Le voci finali -1 non contengono nodi, quindi la risposta per [7, -1, -1] è [[7]], non [[7], []].

Domande frequenti4

Qual è la complessità temporale della visita in ordine di livello di un albero binario?

Sia la soluzione in ampiezza sia quella in profondità visitano ogni nodo una volta, quindi hanno una complessità temporale di O(n) per n nodi. La risposta stessa contiene n valori, quindi lo spazio è O(n). Oltre a ciò, la coda contiene al massimo circa il livello più ampio e la ricorsione al massimo l’altezza dell’albero.

Come fai a sapere dove termina un livello in una ricerca in ampiezza?

Leggi la dimensione della coda all’inizio di ogni round. In quel momento la coda contiene esattamente i nodi di un livello, quindi estrarne quel numero significa estrarre il livello e nient’altro. Funzionano anche altri due metodi: mantieni il livello corrente e quello successivo in due liste separate, oppure inserisci un marcatore dopo ogni livello.

È possibile eseguire una visita in ordine di livello con la ricerca in profondità?

Sì. Passa a ogni nodo la sua profondità e aggiungi il suo valore alla lista corrispondente a quella profondità. Finché la visita percorre il sottoalbero sinistro prima di quello destro, ogni lista risulta ordinata da sinistra a destra. È anche O(n); la visita in ampiezza è più adatta perché produce i livelli in ordine.

L'array è già memorizzato livello per livello. Perché non leggerlo a fette?

Per questo formato funziona: il livello d occupa gli indici da 2^d-1 a 2^(d+1)-2, quindi puoi raccogliere i valori non vuoti di ogni intervallo e fermarti al primo intervallo senza valori. In un colloquio, però, l'albero è solitamente rappresentato da oggetti nodo con puntatori a sinistra e a destra, senza indici su cui suddividerlo. La visita basata su coda è quella che si applica anche a questa forma e a varianti come l'ordine a zigzag o la vista dal lato destro.

Python

def levelOrder(tree):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Atteso

[[4], [9, 2], [6, 8, 5], [3]]