Top View of Binary Tree

Q: Qual è la complessità temporale della vista dall’alto di un albero binario?

Una ricerca in ampiezza visita ciascuno degli n nodi una volta, con una ricerca nella mappa in O(1) per nodo, quindi richiede un tempo O(n) se tieni traccia della colonna più piccola e di quella più grande. Una mappa ordinata delle colonne richiede O(n log w) per w colonne.

MedioVisita di alberi Hashing

+10

Hai un albero binario memorizzato nell'array root in ordine heap: la radice all'indice 0, i figli dell'indice i agli indici 2*i+1 (sinistro) e 2*i+2 (destro), e -1 per una posizione vuota.

La radice si trova nella colonna 0; un figlio sinistro si trova una colonna a sinistra del genitore, mentre un figlio destro si trova una colonna a destra. Guardando dall'alto, vedi il nodo meno profondo di ciascuna colonna; in caso di parità, quello che viene prima nel suo livello da sinistra a destra (l'indice minore). Restituisci i valori che vedi, dalla colonna più a sinistra a quella più a destra.

Funzione

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

rootinteger-array: l’albero in ordine di heap, con -1 per una posizione vuota
Restituisceinteger-array: il valore visto dall'alto in ciascuna colonna, iniziando dalla colonna più a sinistra

Vincoli

1 ≤ root.length ≤ 32767
Ogni root[i] è -1 oppure un valore con 0 ≤ root[i] ≤ 10⁴, e nessun valore compare due volte.
root[0] non è mai -1, quindi l’albero ha almeno un nodo.
L'array potrebbe terminare con voci -1 aggiuntive dopo l'ultimo nodo.
Entrambi i figli di un posto vuoto sono vuoti anch’essi, e l’albero ha al massimo 14 livelli.

Esempi

Input: root = [5, 2, 9, 4, 7, 1, 6]
Output: [4, 2, 5, 9, 6]
Spiegazione: Da sinistra a destra, le colonne contengono 4 (colonna -2), 2 (-1), la radice 5 (0), 9 (1) e 6 (2). Anche 7 e 1 si trovano nella colonna 0, ma la radice è sopra di loro.

Input: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Output: [2, 1, 4]
Spiegazione: 2 si trova nella colonna -1. Il suo figlio destro 3, all’indice 4, torna nella colonna 0, sotto la radice, quindi è nascosto. 4, all’indice 10, il figlio destro di 3, è da solo nella colonna 1.

Input: root = [6, -1, -1]
Output: [6]
Spiegazione: Gli indici 1 e 2 contengono -1, quindi 6 resta da solo nella colonna 0 ed è l'intera vista.

Per approfondire

Con gli oggetti nodo invece di un array, non c’è alcun indice per risolvere un pareggio. Come enunceresti la regola per i pareggi e il tuo codice di ricerca in ampiezza cambierebbe?

Soluzione

Ogni colonna mostra il nodo più superficiale e, in caso di parità, quello che viene prima nell’ordine per livelli. Questo è esattamente l’ordine in cui una ricerca in ampiezza visita i nodi, quindi il primo nodo che la ricerca incontra in una colonna è la risposta. Va bene anche una visita in profondità, ma deve tenere traccia delle profondità e risolvere con attenzione i casi di parità.

Ricerca in profondità, nodo più superficiale per colonna

Intuizione

Percorri l’albero in profondità, tenendo traccia per ogni nodo della colonna e della profondità, e conserva, per ogni colonna, la profondità e il valore del nodo meno profondo trovato finora.

Sostituisci il valore solo se la profondità è strettamente minore. Tra due nodi a pari profondità, quello che compare per primo nell’ordine per livelli viene raggiunto per primo da una visita che esplora ogni sottoalbero sinistro prima del corrispondente sottoalbero destro, perché nel punto in cui i due percorsi divergono procede a sinistra. Sostituendo il valore anche a parità di profondità, vince il nodo visitato dopo: con l’indice 3 vuoto e nodi agli indici 19 e 23, entrambi si trovano nella colonna -2 alla profondità 4, e la risposta è il nodo all’indice 19.

Le colonne occupate formano un intervallo continuo, perché un nodo nella colonna -3 ha antenati nelle colonne -1 e -2; quindi tieni traccia della colonna più piccola e di quella più grande. Ogni nodo viene visitato una volta, tempo O(n), e la ricorsione raggiunge una profondità di circa h chiamate.

Algoritmo

Visita la radice con la colonna 0 e la profondità 0. Ritorna subito se l'indice è fuori dall'array o contiene -1.
Se la colonna non ha ancora un nodo, oppure questa profondità è strettamente minore di quella memorizzata, memorizza questa profondità e questo valore.
Visita 2i+1 con la colonna col-1, poi 2i+2 con la colonna col+1, un livello più in profondità.
Restituisci i valori memorizzati dalla colonna più piccola alla più grande.

def topView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the shallowest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first in level order.
        if col not in best or depth < best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Ricerca in ampiezza, primo nodo per colonna

Intuizione

Una coda che prende la radice, poi il figlio sinistro di ogni nodo e poi il figlio destro, rilascia i nodi in ordine per livelli: ogni nodo di profondità d prima di qualsiasi nodo di profondità d+1, e ogni livello da sinistra a destra. Questa è la priorità del problema, quindi il primo nodo che una colonna riceve è quello visto dall’alto, mentre tutti i successivi vengono ignorati.

Ogni nodo richiede una ricerca nella mappa, per un totale di O(n). La coda può contenere un intero livello, fino a circa metà dei nodi, quindi lo spazio è O(n).

Algoritmo

Inserisci la coppia (indice 0, colonna 0) in una coda.
Estrai una coppia (i, col). Se la mappa non contiene una voce per col, memorizza lì root[i].
Aggiungi (2i+1, col-1), poi (2i+2, col+1), per ogni figlio esistente.
Quando la coda è vuota, restituisci i valori della mappa dalla colonna più piccola alla più grande.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [top[col] for col in range(min(top), max(top) + 1)]

Trappole e casi limite

Mantenere il primo nodo trovato da una visita in profondità. Se il figlio sinistro della radice ha un figlio destro che a sua volta ha un figlio destro (colonna 1, profondità 3), la visita lo incontra prima del figlio destro della radice (colonna 1, profondità 1).
Accodare prima il figlio destro: in caso di parità, viene scelto il nodo sbagliato.
Ordinare le colonne come testo: "-1" viene prima di "-2".
Supporre che il sottoalbero sinistro occupi le colonne negative. Nell'esempio 2 il nodo 4 si trova nel sottoalbero sinistro della radice e nella colonna 1.

Domande frequenti3

Qual è la vista dall'alto di un albero binario?

Numera le colonne a partire dalla radice da 0, una a sinistra per un figlio sinistro e una a destra per un figlio destro. La vista dall'alto elenca, per ogni colonna da sinistra a destra, il nodo più vicino alla radice.

Qual è la complessità temporale della vista dall’alto di un albero binario?

Una ricerca in ampiezza visita ciascuno degli n nodi una volta, con una ricerca nella mappa in O(1) per nodo, quindi richiede un tempo O(n) se tieni traccia della colonna più piccola e di quella più grande. Una mappa ordinata delle colonne richiede O(n log w) per w colonne.

In che modo la vista dall’alto è diversa dalla vista da sinistra e dalla vista dal basso?

La vista da sinistra seleziona il primo nodo di ogni livello. La vista dall’alto seleziona il nodo meno profondo di ogni colonna. La vista dal basso seleziona il nodo più profondo per ogni colonna, quindi una ricerca in ampiezza lo sovrascrive in ogni colonna invece di mantenere il primo nodo.

def topView(root):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

root = [5, 2, 9, 4, 7, 1, 6]

Output atteso

[4, 2, 5, 9, 6]