Binary Tree Level Order Traversal

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

Entrambe le soluzioni visitano ogni nodo una volta: tempo O(n) per n nodi. La risposta contiene n valori, quindi lo spazio è O(n) . Oltre a ciò, la coda contiene circa il livello più ampio e la ricorsione l'altezza dell'albero.

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

Leggi la dimensione della coda all’inizio di ogni round e preleva esattamente quel numero di nodi. Funzionano anche altri due metodi: mantieni il livello corrente e quello successivo in due liste separate, oppure inserisci un marcatore nella coda dopo ogni livello.

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

Per questo formato funziona così: il livello d , con la radice a 0, riempie gli indici da 2^d-1 a 2^(d+1)-2 , quindi raccogli i valori non vuoti di ogni intervallo finché un intervallo non ne contiene nessuno. Nei colloqui di solito si usano invece oggetti nodo con puntatori, e solo la coda si applica anche a quel formato.

MedioVisita di alberi Coda

+10

L'array tree 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 voci -1 in coda.

Restituisci i valori dei nodi livello per livello: un elenco per ogni livello, dalla radice fino al livello più profondo, ciascuno con i suoi valori da sinistra a destra.

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 più alto, 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 l’albero ha almeno un nodo.
L'array può terminare con voci -1 aggiuntive dopo l'ultimo nodo.
Entrambi i figli di una casella vuota sono vuoti anch’essi, 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: L'indice 3 è vuoto, quindi 9 ha solo un figlio destro, 6. Il terzo livello è composto da 6, 8, 5 e dal 3 all'indice 9, sotto 6, che è da solo al quarto livello.

Input: tree = [7, -1, -1]
Output: [[7]]
Spiegazione: Entrambi i figli della radice sono -1, quindi l'albero è composto dal solo 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.

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 essere rappresentato come un elenco da sinistra a destra. Una ricerca in ampiezza con una coda visita i nodi in quest’ordine e, all’inizio di ogni iterazione, la coda contiene esattamente un livello, quindi la sua dimensione indica quanti nodi prendere. Funziona anche una visita in profondità che tiene traccia della profondità di ogni nodo.

In profondità, ordinato per profondità

Intuizione

Attraversa l’albero in profondità, passando a ogni nodo la sua profondità, 0 per la radice, e mantieni una lista per ogni profondità. Un nodo alla profondità d aggiunge il proprio valore alla lista d, iniziando quella lista se è il primo nodo incontrato al suo livello.

Ogni lista risulta ordinata da sinistra a destra, perché la visita termina il sottoalbero sinistro di un nodo prima di entrare in quello destro. Tra due nodi dello stesso livello, viene raggiunto per primo quello il cui percorso svolta a sinistra nel punto in cui i percorsi si separano. Nell’esempio 1, l’ordine di visita 4, 9, 6, 3, 2, 8, 5 riempie [4], [9, 2], [6, 8, 5], [3].

Ogni nodo viene visitato una volta: tempo O(n), con una ricorsione profonda quanto l’albero, al massimo 14 livelli.

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

Ampiezza prima, un livello per turno

Intuizione

Estrai un nodo dalla coda e inserisci i suoi figli, prima quello a sinistra. Il livello d+1 entra solo quando il livello d esce, quindi i nodi escono livello per livello, da sinistra a destra.

Per dividere questo flusso in livelli, leggi la dimensione della coda all'inizio di un round. Il livello precedente è scomparso e nessun nodo del livello successivo è ancora arrivato, quindi la coda contiene esattamente il livello corrente. Estrai quel numero di nodi e disponili in una riga; i loro figli aspettano il round successivo. Nell'esempio 1 i round estraggono 1, 2, 3 e 1 nodi.

Ogni nodo entra ed esce dalla coda una volta: tempo O(n). La coda contiene circa un livello, al massimo 8,192 nodi al livello più profondo di un albero completo di 14 livelli.

Algoritmo

Inserisci in una coda l'indice 0 della radice.
Finché la coda non è vuota, leggi la sua dimensione s e inizia una riga vuota.
Estrai s indici. Per ogni indice i, aggiungi tree[i] alla riga.
Aggiungi 2i+1, poi 2i+2, alla coda se l'indice è all'interno dell'array e non contiene -1.
Aggiungi la riga alla risposta e inizia il round 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

Leggere la dimensione della coda mentre la svuoti. In while (j < queue.length) la lunghezza aumenta man mano che arrivano i figli, quindi il livello successivo confluisce nella riga corrente.
Aggiungere il figlio destro prima di quello sinistro, oppure visitare prima il sottoalbero destro. Nel secondo livello dell'Esempio 1 si ottiene quindi [2, 9].
Saltare il controllo dei limiti child < n. I figli dei nodi più profondi si trovano oltre la fine dell'array.
Rimuovere elementi dall'inizio di una normale lista basata su array, operazione che in molti linguaggi sposta l'intera coda ogni volta. Usa una vera coda o un indice di testa.
Trattare -1 come un nodo. Non viene mai inserito in una riga né nella coda: [7, -1, -1] dà [[7]], non [[7], []].

Domande frequenti3

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

Entrambe le soluzioni visitano ogni nodo una volta: tempo O(n) per n nodi. La risposta contiene n valori, quindi lo spazio è O(n). Oltre a ciò, la coda contiene circa il livello più ampio e la ricorsione l'altezza dell'albero.

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

Leggi la dimensione della coda all’inizio di ogni round e preleva esattamente quel numero di nodi. Funzionano anche altri due metodi: mantieni il livello corrente e quello successivo in due liste separate, oppure inserisci un marcatore nella coda dopo ogni livello.

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

Per questo formato funziona così: il livello d, con la radice a 0, riempie gli indici da 2^d-1 a 2^(d+1)-2, quindi raccogli i valori non vuoti di ogni intervallo finché un intervallo non ne contiene nessuno. Nei colloqui di solito si usano invece oggetti nodo con puntatori, e solo la coda si applica anche a quel formato.

def levelOrder(tree):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

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