Bottom View of Binary Tree

Q: Qual è la complessità temporale della vista inferiore di un albero binario?

O(n) per n nodi: la ricerca in ampiezza gestisce ogni nodo una volta con una scrittura nella mappa hash. Una mappa ordinata, come una mappa ad albero, aggiunge un fattore log w per w colonne.

MedioVisita di alberi Hashing

+10

L’array root contiene un albero binario: la radice all’indice 0, i figli dell’indice i agli indici 2i+1 (sinistra) e 2i+2 (destra), -1 per una posizione vuota e, eventualmente, altre voci -1 alla fine.

La radice si trova nella colonna 0; un passo a sinistra sposta di una colonna a sinistra, un passo a destra di una colonna a destra. Vista dal basso, ogni colonna mostra il nodo più profondo e, in caso di parità, l’ultimo su quel livello letto da sinistra a destra (l’indice più grande). Restituisci i valori che vedi, iniziando dalla colonna più a sinistra.

Funzione

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

rootinteger-array: l’albero in ordine di heap, con -1 per una posizione vuota
Restituisceinteger-array: il valore osservato dal basso in ciascuna colonna, partendo dalla colonna più a sinistra

Vincoli

1 ≤ root.length ≤ 32767
Ciascun 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 può terminare con voci -1 aggiuntive dopo l’ultimo nodo.
Entrambi i figli di una posizione vuota 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, 1, 9, 6]
Spiegazione: La colonna 0 contiene 5 e, due livelli più in basso, 7 (indice 4) e 1 (indice 5). 1 viene dopo sul livello condiviso, quindi è quello che appare. Le colonne -2, -1, 1 e 2 contengono 4, 2, 9 e 6.

Input: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Output: [5, 4, 3]
Spiegazione: La colonna -1 contiene 2 e, due livelli più in basso, 5 (indice 9), quindi vedi 5. Nella colonna 0, 4 si trova sotto la radice. La colonna 1 contiene solo 3.

Input: root = [8, -1, -1, -1]
Output: [8]
Spiegazione: Ogni posizione dopo la radice è -1, quindi 8 è l'unico nodo e la colonna 0 è l'unica colonna.

Per approfondire

Se in caso di parità al livello più profondo di una colonna dovrebbero essere restituiti tutti i nodi a pari merito, da sinistra a destra, come cambierebbe la versione con ricerca in ampiezza? Quali nodi restituirebbe la colonna 0 dell’esempio 1?

Soluzione

Ogni colonna mostra il suo nodo più profondo e, in caso di parità, vince il nodo che viene dopo nell’ordine per livelli. Una ricerca in ampiezza visita i nodi in ordine per livelli, quindi l’ultimo nodo che visita in una colonna è la risposta: fai sovrascrivere a ogni nodo lo slot della sua colonna.

Ricerca in profondità, nodo più profondo per colonna

Intuizione

Percorri l’albero in profondità, assegnando a ogni nodo la sua colonna e profondità, e tieni traccia, per ogni colonna, della profondità e del valore del nodo più profondo incontrato finora.

Visitare il sottoalbero sinistro prima di quello destro incontra i nodi di un livello da sinistra a destra, quindi il nodo che vuoi è l’ultimo incontrato: sostituisci quando la profondità è maggiore o uguale. Nell’esempio 1, la visita incontra 7 e poi 1, entrambi a profondità 2 nella colonna 0, e 1 prende la colonna.

Le colonne formano un intervallo continuo, quindi tieni traccia della più piccola e della più grande e leggi ogni colonna compresa tra queste. Una visita per nodo richiede un tempo O(n), e la ricorsione ha una profondità di h chiamate per un albero di h livelli.

Algoritmo

Visita la radice con colonna 0 e profondità 0.
Salta l'indice i quando supera la fine dell'array oppure root[i] è -1.
Se la colonna non contiene ancora un nodo, o questa profondità è maggiore o uguale a quella memorizzata, memorizza questa profondità e questo valore.
Visita 2i+1 con la colonna col-1, poi 2i+2 con la colonna col+1, entrambi a un livello di profondità in più.
Restituisci i valori memorizzati, iniziando dalla colonna più piccola.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later 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, ultimo nodo per colonna

Intuizione

Una coda in cui ogni nodo, quando esce, aggiunge il figlio sinistro e poi quello destro restituisce i nodi in ordine di livello: ogni nodo di profondità d prima di qualsiasi nodo di profondità d+1, e ogni livello da sinistra a destra. Tra i nodi di una colonna, quello più profondo esce per ultimo e, a parità di profondità, esce per ultimo quello più a destra. Quindi, quando ogni nodo sovrascrive la posizione della propria colonna, ogni posizione finisce per contenere il nodo visto dal basso, senza dover confrontare le profondità.

Nell'esempio 1, 7 scrive nella colonna 0 e 1 lo sovrascrive.

Ogni nodo comporta una visita della coda e una scrittura nella mappa: tempo O(n). La coda può contenere un intero livello, 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) e memorizza root[i] sotto col, sostituendo qualsiasi valore precedente.
Aggiungi (2i+1, col-1), poi (2i+2, col+1), per ogni figlio che si trova nell’array e non è -1.
Ripeti finché la coda non è vuota, tenendo traccia della colonna più piccola e di quella più grande.
Restituisci i valori della mappa, iniziando dalla colonna più piccola.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last 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 deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[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 [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Trappole e casi limite

Sostituire solo a una profondità strettamente maggiore nella versione con ricerca in profondità. Nell’esempio 1 si mantiene quindi 7 invece di 1.
Mantenere il primo nodo che una ricerca in ampiezza incontra per ogni colonna. Questa è la vista dall’alto.
Aggiungere alla coda il figlio destro prima di quello sinistro. Ogni livello viene quindi elaborato da destra a sinistra e, in caso di parità, viene scelto il nodo sbagliato.
Considerare le foglie come risposta. Nell’esempio 1 la foglia 7 è nascosta da 1 e, nell’esempio 2, il nodo 4 ha un figlio, ma si trova in fondo alla colonna 0.
Ordinare le colonne come testo. Come stringhe, "-10" si trova tra "-1" e "-2".

Domande frequenti3

Qual è la vista dal basso di un albero binario?

Assegna alla colonna della radice il valore 0, a ogni passo a sinistra una colonna in meno e a ogni passo a destra una colonna in più. La vista dal basso elenca il nodo più profondo di ogni colonna, da sinistra a destra. Questo problema risolve le parità di profondità in base all’ordine per livello, mantenendo il nodo successivo.

Qual è la complessità temporale della vista inferiore di un albero binario?

O(n) per n nodi: la ricerca in ampiezza gestisce ogni nodo una volta con una scrittura nella mappa hash. Una mappa ordinata, come una mappa ad albero, aggiunge un fattore log w per w colonne.

Qual è la differenza tra la vista dall'alto e la vista dal basso?

Entrambe selezionano un nodo per colonna. La vista dall’alto seleziona il nodo più superficiale e quella dal basso il più profondo. Nella versione in ampiezza, la vista dall’alto conserva il primo valore ricevuto da una colonna; quella dal basso lo sovrascrive ogni volta.

def bottomView(root):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

[4, 2, 1, 9, 6]