Vertical Order Traversal of a Binary Tree

DifficileVisita di alberi Ordinamento Hashing

+10

Un albero binario è memorizzato nell'array root in ordine heap: la radice si trova all'indice 0, i figli dell'indice i si trovano rispettivamente in 2*i+1 (sinistra) e 2*i+2 (destra), -1 indica una posizione vuota e l'array può terminare con ulteriori elementi -1.

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. Restituisci una lista per ogni colonna, da sinistra a destra. All'interno di una colonna, elenca i nodi dall'alto verso il basso e, tra i nodi che condividono la stessa colonna e profondità, in ordine crescente di valore.

Funzione

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: l'albero in ordine heap, con -1 per una posizione vuota
Restituisceinteger-2d-array: un elenco di valori per ogni colonna, iniziando dalla colonna più a sinistra e procedendo dall’alto verso il basso

Vincoli

1 ≤ root.length ≤ 32767
Ogni root[i] è -1 oppure un valore con 0 ≤ root[i] ≤ 5000, 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 oltre 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 = [5, 2, 9, 4, 7, 1, 6]
Output: [[4], [2], [5, 1, 7], [9], [6]]
Spiegazione: La colonna 0 contiene la radice 5, poi 7 e 1 due livelli più in basso. Questi due condividono la colonna e la profondità, quindi 1 viene prima di 7, anche se 7 è più a sinistra.

Input: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Output: [[2, 5], [1, 4], [3]]
Spiegazione: La colonna -1 contiene 2 alla profondità 1 e 5 alla profondità 3 (il figlio sinistro di 4). La colonna 0 contiene la radice 1 e 4 all'indice 4. La colonna 1 contiene solo 3.

Input: root = [6, -1, -1]
Output: [[6]]
Spiegazione: 6 non ha elementi figli, quindi la risposta ha una sola colonna, [6].

Per approfondire

Ogni valore è al massimo 5000. Puoi sfruttare questo fatto per eliminare l’ordinamento per confronto e completare in tempo O(n + 5000)?

Soluzione

Ogni nodo ha tre chiavi: colonna, profondità e valore. La risposta è costituita dai nodi ordinati in base a queste chiavi, con un elenco per colonna. In caso di parità per colonna e profondità, l’ordine dipende dal valore, non dall’ordine da sinistra a destra in cui li incontra una visita, quindi devi ordinare tutti i nodi insieme oppure ogni livello di una ricerca in ampiezza.

Registra ogni nodo, poi ordina

Intuizione

Visita ogni nodo una volta, in qualsiasi ordine, e registra la tripla (colonna, profondità, valore). Un passo verso un figlio aggiunge 1 alla profondità e sposta la colonna di 1 a sinistra o a destra. Poi ordina le triple per colonna, profondità e valore. I nodi di ogni colonna si trovano ora insieme, nell'ordine richiesto. Scorri l'elenco ordinato e avvia una nuova lista interna ogni volta che cambia la colonna.

Nell'esempio 1, le triple della colonna 0 vengono ordinate così: (0, 0, 5), (0, 2, 1), (0, 2, 7). L'ordinamento, O(n log n), domina la scansione O(n), e le triple occupano uno spazio O(n).

Algoritmo

Inserisci (indice 0, colonna 0, profondità 0) in uno stack.
Estrai un nodo, registra (colonna, profondità, valore) e inserisci ogni figlio reale con colonna col-1 o col+1 e profondità depth+1.
Quando lo stack è vuoto, ordina le triple per colonna, poi per profondità e infine per valore.
Percorrile, iniziando una nuova lista ogni volta che cambia la colonna.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Livello per livello, ordina all'interno di ogni livello

Intuizione

Una ricerca in ampiezza gestisce un livello alla volta. Se ogni nodo aggiunge il proprio valore all’elenco della propria colonna quando viene gestito, ogni elenco è già ordinato dall’alto verso il basso, quindi non serve ordinare per profondità. Le parità si verificano solo all’interno dello stesso livello, quindi ordina ogni livello per colonna e poi per valore, prima di gestirlo.

Nell’esempio 1, il livello 2 arriva come 4, 7, 1, 6 nelle colonne -2, 0, 0, 2 e viene ordinato come 4, 1, 7, 6, quindi la colonna 0 diventa [5, 1, 7]. Le colonne occupate formano un intervallo continuo, quindi è sufficiente tenere traccia della più piccola e della più grande.

Ordinare un livello di m nodi costa O(m log m). Il caso peggiore è comunque O(n log n), perché l’ultimo livello di un albero completo contiene circa metà dei nodi. Lo spazio è O(n).

Algoritmo

Inizia con un livello contenente (indice 0, colonna 0).
Ordina il livello per colonna, poi per valore.
In quest’ordine, aggiungi ogni valore all’elenco della sua colonna e raccogli i suoi figli reali, con colonne col-1 e col+1, nel livello successivo.
Ripeti finché un livello non è vuoto, tenendo traccia della colonna più piccola e di quella più grande.
Restituisci gli elenchi dalla colonna più piccola a quella più grande.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Trappole e casi limite

Lasciare le parità nell’ordine da sinistra a destra. Una ricerca in ampiezza senza l’ordinamento per livello restituisce [5, 7, 1] per la colonna 0 dell’esempio 1, non [5, 1, 7].
Aggiungere i valori durante una visita in profondità senza ordinamento. In [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], una visita che procede prima a sinistra aggiunge 5 (profondità 3) alla colonna 1 prima di 3 (profondità 1).
Ordinare per colonna e valore, ma non per profondità. La colonna 0 dell’esempio 1 diventa quindi [1, 5, 7].
Usare stringhe come chiavi delle colonne. In ordine alfabetico, "-1" viene prima di "-2", quindi le colonne a sinistra di 0 risultano nell’ordine sbagliato.

Domande frequenti3

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

Ordinare tutti i nodi per colonna, profondità e valore ha un costo di O(n log n) e domina la visita O(n). Ordinare livello per livello ha lo stesso caso peggiore, perché l’ultimo livello di un albero completo contiene circa metà dei nodi. Lo spazio è O(n).

È possibile eseguire una visita in ordine verticale senza ordinare?

Solo se le parità vengono risolte da sinistra a destra. In tal caso, una ricerca in ampiezza che aggiunge ogni valore all'elenco della sua colonna dà la risposta in O(n). Se le parità sono ordinate per valore, serve un po' di ordinamento, ma solo all'interno di un livello, poiché solo i nodi dello stesso livello possono essere in parità.

In che modo la visita in ordine verticale è correlata alla vista dall’alto e alla vista dal basso?

Tutti e tre raggruppano i nodi in base allo stesso numero di colonna. La vista dall’alto mantiene il nodo più superficiale di ogni colonna, mentre la vista dal basso mantiene quello più profondo. La visita in ordine verticale mantiene tutti i nodi e, quando più nodi condividono un livello, li ordina per valore, mentre le viste scelgono in base alla posizione.

def verticalTraversal(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, 1, 7], [9], [6]]