Left View of Binary Tree

+10

Hai un albero binario rappresentato dall’array root in ordine di heap: la radice si trova all’indice 0, i figli dell’indice i si trovano agli indici 2*i+1 (sinistro) e 2*i+2 (destro), e -1 indica una posizione vuota. L’array può terminare con voci -1 aggiuntive.

Mettiti a sinistra dell’albero. A ogni livello vedi un nodo, quello più a sinistra; il resto del livello è nascosto dietro di esso. Restituisci i valori che vedi, dal livello più alto a quello più basso.

Funzione

leftView(root: integer-array) → integer-array

rootinteger-array: l'albero in ordine heap, con -1 per una posizione vuota
Restituisceinteger-array: il valore più a sinistra di ogni livello, a partire dal livello superiore

Vincoli

1 ≤ root.length ≤ 32767
Ogni root[i] è -1 oppure un valore con 0 ≤ root[i] ≤ 10⁴.
I valori dei nodi sono distinti.
root[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 posizione vuota sono vuoti anche loro, e l'albero ha al massimo 14 livelli.

Esempi

Input: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Output: [3, 8, 6, 1]
Spiegazione: 8 è una foglia, quindi il terzo e il quarto livello contengono solo 6 (indice 6) e 1 (indice 13), entrambi sotto il figlio destro 5. Li vedi comunque: [3, 8, 6, 1].

Input: root = [10, -1, -1]
Output: [10]
Spiegazione: Gli indici 1 e 2 contengono -1, quindi 10 non ha figli e la vista mostra solo la radice.

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 2, 4]
Spiegazione: Un albero completo di tre livelli. Le posizioni più a sinistra dei livelli sono gli indici 0, 1 e 3, che contengono 1, 2 e 4.

Per approfondire

Il livello d riempie gli indici da 2^d-1 a 2^(d+1)-2. Riesci a costruire la vista scorrendo quegli intervalli, senza usare una coda o la ricorsione? Quanto costa su un array con padding?

Soluzione

Seguire i figli sinistri dalla radice non funziona quando il sottoalbero sinistro è più corto: nel primo esempio i livelli inferiori si vedono attraverso il sottoalbero destro. Vuoi il primo nodo di ogni livello. La ricerca in ampiezza ti restituisce ogni livello da sinistra a destra; una visita in profondità che procede prima a sinistra incontra per primo il nodo più a sinistra di ogni livello.

Ricerca in ampiezza, primo nodo di ogni livello

Intuizione

Una coda elaborata per turni ti fornisce i livelli uno alla volta. All'inizio di un turno la coda contiene esattamente un livello, da sinistra a destra, perché ogni elemento figlio aggiunto durante il turno viene inserito dietro di esso. Estrai quel numero di indici, aggiungi alla coda i figli di ciascuno partendo da sinistra e conserva il primo valore.

Nel primo esempio i turni sono [3], [8, 5], [6] e [1], e conservano rispettivamente 3, 8, 6 e 1. 8 non aggiunge nulla, perché le posizioni dei suoi figli 3 e 4 contengono -1.

Ogni nodo entra ed esce dalla coda una volta: tempo O(n). La coda contiene un intero livello, fino a 8192 indici in un albero completo di 14 livelli.

Algoritmo

Inizia una coda contenente l’indice 0 e una risposta vuota.
Finché la coda non è vuota, poni s uguale alla sua dimensione e rimuovi s indici. Aggiungi il valore del primo.
Per ogni indice rimosso i, metti in coda 2i+1 e poi 2i+2, saltando gli indici oltre la fine e le voci uguali a -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

In profondità, prima il figlio sinistro

Intuizione

Visita l’albero in profondità, prima il sottoalbero sinistro e poi quello destro, e passa la profondità di ogni nodo. Il primo nodo raggiunto dalla visita alla profondità d è il più a sinistra al livello d. Prendi il nodo più a sinistra x di un livello e un qualsiasi nodo y alla sua destra: nell’ultimo nodo in cui i loro percorsi coincidono, x va a sinistra e y a destra, e la visita completa il ramo sinistro prima di svoltare a destra.

La visita scende di un livello alla volta, quindi quando raggiunge per la prima volta la profondità d, la risposta contiene esattamente d valori. Registra un nodo quando d è uguale alla lunghezza della risposta; non serve tenere un insieme delle profondità già viste.

Ogni nodo viene visitato una volta, tempo O(n), e la memoria contiene una chiamata per livello, al massimo 14 qui. La versione R mantiene il proprio stack e inserisce prima il figlio destro e poi quello sinistro.

Algoritmo

Crea una risposta vuota e chiama visit(0, 0).
In visit(i, d), restituisci subito se i è fuori dall'array o se root[i] è -1.
Se d è uguale alla lunghezza della risposta, la visita ha raggiunto il livello d per la prima volta: aggiungi root[i].
Chiama visit(2i+1, d+1), poi visit(2i+2, d+1).
Restituisci la risposta una volta terminata la prima chiamata.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Trappole e casi limite

Seguire solo i figli sinistri a partire dalla radice. Nel primo esempio ci si ferma a 8 e si perdono 6 e 1.
Leggere il primo slot di ogni livello, root[2^d-1]. Nel primo esempio, il primo slot del terzo livello, indice 3, contiene -1, mentre il suo unico nodo si trova all'indice 6.
Visitare prima il figlio destro nella visita in profondità. Il primo nodo incontrato a ogni livello è quindi il più a destra.
Leggere un figlio senza controllare i limiti. Il 1 all'indice 13 ha posizioni per i figli 27 e 28, oltre la fine dell'array di 14 elementi.

Domande frequenti3

La vista a sinistra è uguale al limite sinistro di un albero?

No. Il confine sinistro è un percorso: parte dal figlio sinistro della radice, va a sinistra quando può, altrimenti a destra, e si ferma prima di una foglia. La vista sinistra prende un nodo per livello da qualsiasi ramo. Nel primo esempio il confine è vuoto, poiché 8 è una foglia, ma la vista mostra 8, 6 e 1.

Qual è la complessità temporale e spaziale della vista sinistra?

Entrambe le soluzioni visitano ogni nodo una volta, quindi il tempo è O(n). La coda della visita in ampiezza contiene un intero livello, circa la metà dei nodi di un albero completo. La visita in profondità da sinistra mantiene una chiamata per livello, O(h) per h livelli.

Come modifichi la soluzione per ottenere la visualizzazione corretta?

Nella versione in ampiezza, conserva l’ultimo valore di ogni livello invece del primo. Nella versione in profondità, visita il figlio destro prima di quello sinistro; il primo nodo raggiunto dalla visita a ogni livello sarà quindi quello più a destra.

def leftView(root):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Output atteso

[3, 8, 6, 1]