Construct Binary Tree from Preorder and Inorder Traversal

Q: Perché hai bisogno sia del preordine sia dell’inordine per ricostruire un albero binario?

Il preorder da solo non determina la forma. Il preorder [1, 2] è compatibile con un albero in cui 2 è il figlio sinistro di 1 e con uno in cui è il figlio destro. L’inorder risolve l’ambiguità: [2, 1] colloca 2 a sinistra, [1, 2] a destra. Con valori distinti, la coppia descrive esattamente un albero.

Q: Riesci a ricostruire un albero binario a partire da una visita in preorder e una in postorder?

Non in generale. La visita in preorder [1, 2] e la visita in postorder [2, 1] sono compatibili sia con un figlio sinistro sia con un figlio destro, perché nessuna delle due visite colloca la radice tra i suoi sottoalberi. La coppia è sufficiente solo per un albero binario pieno, in cui ogni nodo ha zero o due figli.

MedioVisita di alberi Hashing Ricorsione

+10

Ricevi due array, preorder e inorder, che elencano i valori distinti dello stesso albero binario. La visita in preorder visita un nodo, poi il suo sottoalbero sinistro e infine quello destro. La visita in inorder visita il sottoalbero sinistro, poi il nodo e infine il sottoalbero destro.

Ricostruisci l'albero e restituiscilo come array in ordine per livelli: la radice all'indice 0, i figli dell'indice i agli indici 2i+1 (sinistro) e 2i+2 (destro), e -1 per ogni posizione vuota. L'array termina con l'ultimo nodo, senza -1 finali.

Funzione

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: i valori in preordine: nodo, sottoalbero sinistro, sottoalbero destro
inorderinteger-array: i valori in ordine: sottoalbero sinistro, nodo, sottoalbero destro
Restituisceinteger-array: l'albero in ordine per livelli, con -1 per le posizioni vuote e senza -1 finali

Vincoli

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴ e tutti i valori sono distinti.
inorder contiene gli stessi valori ed entrambi gli array descrivono lo stesso albero binario.
La profondità dell'albero è al massimo 14, quindi ogni indice nella risposta è inferiore a 2¹⁴-1 = 16383.

Esempi

Input: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Output: [7, 3, 4, 0, 9, -1, 6]
Spiegazione: Il preorder inizia con la radice, 7. Si trova alla posizione inorder 3, quindi 0, 3, 9 vanno a sinistra e 4, 6 vanno a destra. 4 ha solo un figlio destro, 6, quindi l’indice 5 rimane -1.

Input: preorder = [1, 2, 3]inorder = [2, 3, 1]
Output: [1, 2, -1, -1, 3]
Spiegazione: La radice 1 viene per ultima in inorder, quindi l’indice 2 è -1. Tra 2, 3, preorder elenca prima 2 e inorder colloca 3 dopo di esso, quindi 3 è il suo figlio destro, all’indice 4.

Per approfondire

Riesci a ricostruire l’albero senza ricorsione, in un’unica passata su preorder usando una pila esplicita?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Il preorder fornisce la radice di ogni sottoalbero: il primo valore della sua porzione. L’inorder fornisce la divisione: i valori prima della radice vanno a sinistra, quelli dopo vanno a destra. La ricorsione su entrambe le metà ricostruisce l’albero, e una mappa dai valori alle posizioni nell’inorder consente di trovare ogni radice in un solo passaggio.

Dividi ricorsivamente, cercando la radice

Intuizione

Nella visita anticipata, il sottoalbero sinistro segue la sua radice e occupa una voce per ogni valore, m-lo, dove m è la posizione della radice nella visita simmetrica. Il sottoalbero destro viene dopo, quindi la sua radice si trova in pre+1+(m-lo). Nel primo esempio, la parte sinistra 0, 3, 9 contiene tre valori, quindi il sottoalbero destro inizia all'indice 4 della visita anticipata, con il valore 4.

Una profondità massima di 14 mantiene ogni indice di output sotto 2^14-1. Riempi altrettante celle con -1, scrivi ogni valore al suo indice e rimuovi le voci finali -1 alla fine.

Scansionare ogni intervallo della visita simmetrica per trovare la radice ha costo O(n·h): gli intervalli allo stesso livello non si sovrappongono, quindi un livello scansiona al massimo n voci, cioè al massimo 14 × 3000 = 42000 passaggi in questo caso. Senza un limite di profondità, un albero a forma di percorso comporta un costo di O(n²).

Algoritmo

Crea out con 2^14-1 elementi, tutti -1.
Scrivi build(pre, lo, hi, h): se lo > hi, restituisci. Altrimenti scrivi preorder[pre] in out[h].
Scorri inorder da lo per trovare la posizione m della radice. Il sottoalbero sinistro ha m-lo valori.
Chiama build(pre+1, lo, m-1, 2*h+1) e build(pre+1+(m-lo), m+1, hi, 2*h+2).
Chiama build(0, 0, n-1, 0), poi elimina gli elementi -1 finali e restituisci il resto.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Dividi ricorsivamente con una mappa delle posizioni

Intuizione

I valori sono distinti, quindi ciascuno ha esattamente una posizione in inorder. Registrala in una mappa che associa ogni valore alla sua posizione prima che inizi la ricorsione, così ogni ricerca della radice richiederà un solo passaggio.

La creazione della mappa richiede O(n) e poi ogni valore viene inserito una sola volta con un lavoro costante, quindi il tempo totale è O(n). La mappa occupa O(n) spazio e la ricorsione usa un frame per livello. In C e R i valori sono al massimo 10^4, quindi un semplice array di 10^4+1 elementi può fungere da mappa.

Algoritmo

Crea una mappa da ciascun valore di inorder alla sua posizione.
Crea out con 2^14-1 elementi, tutti -1.
In build(pre, lo, hi, h), restituisci il controllo se lo > hi; altrimenti scrivi preorder[pre] in out[h] e cerca la sua posizione m nella mappa.
Richiama ricorsivamente build(pre+1, lo, m-1, 2*h+1) e build(pre+1+(m-lo), m+1, hi, 2*h+2).
Chiama build(0, 0, n-1, 0), poi elimina gli elementi finali -1 e restituisci il resto.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Trappole e casi limite

Avviare il sottoalbero destro a pre+1+m invece che a pre+1+(m-lo). Funziona quando lo è 0, come nella chiamata iniziale, e smette di funzionare quando un intervallo inizia più avanti.
Omettere gli spazi vuoti. Un figlio mancante occupa comunque la sua posizione, quindi il secondo esempio restituisce [1, 2, -1, -1, 3], non [1, 2, 3].
Lasciare voci -1 finali. Restituire tutte le 2^14-1 celle aggiunge 16376 voci -1 extra al primo esempio.
Copiare porzioni di entrambi gli array a ogni chiamata, aggiungendo O(n) per livello. Passa gli intervalli di indici.
In Lua e R, gli array iniziano da 1. Mantieni le posizioni a partire da 0 per i calcoli e leggi preorder[pre + 1] e out[h + 1].

Domande frequenti3

Perché hai bisogno sia del preordine sia dell’inordine per ricostruire un albero binario?

Il preorder da solo non determina la forma. Il preorder [1, 2] è compatibile con un albero in cui 2 è il figlio sinistro di 1 e con uno in cui è il figlio destro. L’inorder risolve l’ambiguità: [2, 1] colloca 2 a sinistra, [1, 2] a destra. Con valori distinti, la coppia descrive esattamente un albero.

Qual è la complessità temporale della creazione di un albero binario a partire da preorder e inorder?

Con una mappa dai valori alle posizioni inordine, la complessità è O(n) in termini di tempo e O(n) di spazio aggiuntivo. Senza la mappa, cercare la radice in ogni intervallo inordine costa O(n·h), che diventa O(n²) in un albero a forma di percorso.

Riesci a ricostruire un albero binario a partire da una visita in preorder e una in postorder?

Non in generale. La visita in preorder [1, 2] e la visita in postorder [2, 1] sono compatibili sia con un figlio sinistro sia con un figlio destro, perché nessuna delle due visite colloca la radice tra i suoi sottoalberi. La coppia è sufficiente solo per un albero binario pieno, in cui ogni nodo ha zero o due figli.

def buildTree(preorder, inorder):
    # Scrivi il codice qui

Test #1

Test #2

Argomenti

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Output atteso

[7, 3, 4, 0, 9, -1, 6]