Invert Binary Tree

Q: Qual è la complessità temporale dell'inversione di un albero binario?

Ogni nodo viene visitato una volta, quindi il tempo è O(n) . Una soluzione ricorsiva usa O(h) di spazio nello stack per un albero di profondità h , mentre una basata su una coda usa O(w) per il livello più ampio. In questa versione con array, la risposta stessa è un nuovo array, che aggiunge O(n) .

FacileVisita di alberi

+10

Ti viene fornito un albero binario memorizzato nell'array tree in ordine per livelli. La radice si trova all'indice 0, i figli del nodo all'indice i si trovano agli indici 2*i+1 (sinistro) e 2*i+2 (destro), -1 indica una posizione vuota e l'array può terminare con voci -1 aggiuntive.

Inverti l'albero: scambia il figlio sinistro e quello destro di ogni nodo, così l'intero albero diventa la sua immagine speculare. Restituisci l'albero invertito nello stesso formato, senza voci -1 alla fine.

Funzione

invertTree(tree: integer-array) → integer-array

treeinteger-array: l'albero binario in ordine per livelli, con -1 per uno spazio vuoto
Restituisceinteger-array: l'albero speculare in ordine per livelli, senza voci -1 finali

Vincoli

1 ≤ tree.length ≤ 16383
Ogni tree[i] è -1 oppure un valore con 0 ≤ tree[i] ≤ 1000.
tree[0] non è mai -1, quindi l’albero ha almeno un nodo.
The array può terminare con voci -1 aggiuntive dopo l’ultimo nodo.
Entrambi i figli di una posizione vuota sono vuoti a loro volta e la profondità è al massimo 14.

Esempi

Input: tree = [5, 3, 8, 1, 4, -1, 9]
Output: [5, 8, 3, 9, -1, 4, 1]
Spiegazione: I figli della radice 3 e 8 si scambiano di posto. Sotto di loro, 1 e 4, che si trovavano sotto 3, tornano come 4 e 1, e 8, che aveva solo un figlio destro 9, ora ce l’ha a sinistra.

Input: tree = [2, 7, -1, 6]
Output: [2, -1, 7, -1, -1, -1, 6]
Spiegazione: La catena 2, 7, 6 pende a sinistra e la sua immagine speculare pende a destra. Il 7 si sposta dall’indice 1 all’indice 2 e il 6 dall’indice 3 all’indice 6, quindi la risposta è più lunga dell’input, con -1 in ogni posizione vuota prima dell’ultimo nodo.

Input: tree = [1, -1, -1]
Output: [1]
Spiegazione: Un singolo nodo è il proprio specchio. Le due voci -1 sono riempitivi e la risposta elimina ogni -1 alla fine.

+14 test nascosti all’invio

Per approfondire

Come verificheresti se un albero è il proprio specchio, usando le stesse coppie di indici ma senza costruire la copia invertita?

Suggerimenti

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

0 di 3 aperti

Soluzione

Rispecchiare un albero significa che ogni nodo scambia il sottoalbero sinistro con quello destro, fino in fondo. Con oggetti nodo basta uno scambio per nodo. In questa rappresentazione con array, la posizione di un nodo è il suo indice, quindi scambiare due sottoalberi significa spostare ogni nodo al loro interno. La soluzione consiste nel costruire la risposta in un nuovo array e copiare ogni nodo direttamente nel suo indice speculare, portando avanti coppie di indici durante una visita: dove si trova ora il nodo e dove deve andare.

Ricorsione che posiziona ogni nodo al suo indice speculare

Intuizione

Per prima cosa, vediamo come spostarsi nell’array. Il nodo all’indice i ha il figlio sinistro all’indice 2*i+1 e il figlio destro all’indice 2*i+2. Un figlio esiste solo se il suo indice è compreso nell’array e il valore in quella posizione non è -1. In [5, 3, 8, 1, 4, -1, 9] la radice 5 ha 3 e 8 agli indici 1 e 2, e il nodo 8 all’indice 2 ha uno spazio vuoto a sinistra all’indice 5 e il nodo 9 all’indice 6.

Ora passiamo al riflesso speculare. La radice resta all’indice 0. Il sottoalbero sinistro di un nodo diventa il sottoalbero destro della sua copia speculare, e il suo sottoalbero destro diventa quello sinistro. Quindi, se il nodo all’indice src finisce all’indice dst nella risposta, il suo figlio sinistro finisce all’indice 2*dst+2 e il suo figlio destro all’indice 2*dst+1. Scrivi place(src, dst): copia il valore, poi chiama place(2*src+1, 2*dst+2) e place(2*src+2, 2*dst+1). Se la posizione è vuota, restituisci subito. Nel primo esempio, il nodo 3 all’indice 1 finisce all’indice 2, quindi il suo figlio sinistro 1 finisce all’indice 6 e il suo figlio destro 4 all’indice 5.

Un nodo non cambia mai livello, quindi il suo indice speculare resta nello stesso livello di quello originale. Arrotonda la lunghezza al numero intero di livelli successivo (1, 3, 7, 15, ...), riempi quel numero di posizioni con -1 e rimuovi alla fine le voci -1 finali. Nel secondo esempio, la lunghezza 4 viene arrotondata a 7, lasciando spazio al 6 all’indice 6.

Ogni nodo viene posizionato una volta e l’output viene riempito e accorciato una volta: tempo O(n) per un array di lunghezza n. L’output richiede memoria O(n) e lo stack delle chiamate O(h), al massimo 14 frame in questo caso, il che rende sicura la ricorsione in questo problema.

Algoritmo

Arrotonda la lunghezza per eccesso a size = 2^k - 1 e riempi un output di quella dimensione con -1.
Scrivi place(src, dst): se src supera la fine o tree[src] è -1, restituisci.
Altrimenti imposta out[dst] = tree[src], poi chiama place(2*src+1, 2*dst+2) e place(2*src+2, 2*dst+1).
Chiama place(0, 0), elimina gli elementi -1 finali e restituisci l'output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

Ricerca in ampiezza con una coda di coppie di indici

Intuizione

Le stesse coppie funzionano senza ricorsione. Inserisci (0, 0) in una coda: la radice e la posizione in cui va. Preleva una coppia (src, dst) dall’inizio, copia tree[src] in out[dst] e inserisci in coda ogni figlio reale con la destinazione scambiata: il figlio sinistro 2*src+1 con 2*dst+2, il figlio destro 2*src+2 con 2*dst+1.

Questa è la classica inversione iterativa. Con oggetti nodo, prelevi un nodo dalla coda, scambi i suoi due figli e li inserisci in coda. Qui lo scambio viene scritto invece nell’indice di destinazione, perché l’array non può scambiare due interi sottoalberi in un solo passaggio. Ogni nodo reale entra nella coda una volta, con la posizione esatta a cui appartiene, quindi l’output finisce per contenere ogni nodo nella sua posizione speculare. Nel primo esempio le coppie risultano (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

Il tempo è O(n). La coda contiene al massimo un livello e poco più, O(w) per il livello più ampio w, oltre all’output O(n). Non c’è uno stack di chiamate che possa andare in overflow, quindi questa versione si applica senza modifiche anche agli alberi profondi basati su puntatori.

Algoritmo

Arrotonda la lunghezza per eccesso al numero intero di livelli e riempi un output di quella dimensione con -1.
Inserisci la coppia (0, 0) in una coda.
Estrai una coppia (src, dst) dall'inizio e imposta out[dst] = tree[src].
Inserisci in coda (2*src+1, 2*dst+2) e (2*src+2, 2*dst+1) per ogni figlio che si trova all'interno dell'array e non è -1.
Quando la coda è vuota, rimuovi le voci -1 finali e restituisci l'output.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Trappole e casi limite

Lo specchio in sé è breve da descrivere. Gli errori dipendono dall'array: dalla sua dimensione, dalla sua fine e da cosa sposta davvero lo scambio di due elementi.

Scambiare tree[2*i+1] e tree[2*i+2] sul posto. In questo modo si scambiano due valori, ma non i sottoalberi che si trovano sotto di essi. Scambiare gli indici 1 e 2 nel primo esempio lascia 1 e 4 appesi sotto 8.
Creare un output lungo quanto l'input. Un nodo specchiato può trovarsi oltre l'ultimo indice dell'input, come accade con 6 nel secondo esempio. Dimensiona l'output in modo che comprenda livelli interi.
Dimenticare di troncare. La risposta non ha -1 alla fine, sia per gli input riempiti con valori di padding sia per gli alberi il cui specchio termina prima dell'input.
Invertire l'intero array. In questo modo si mescolano i livelli: l'ultima foglia diventerebbe la radice.
Saltare il controllo dei limiti. L'indice di un figlio può superare la fine dell'input, perché l'array può terminare subito dopo l'ultimo nodo.
Confondere l'offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici a partire da 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

Che cosa significa invertire un albero binario?

Invertire un albero binario lo trasforma nella sua immagine speculare: in ogni nodo, i sottoalberi sinistro e destro si scambiano di posto. La radice resta dov’è, la foglia più a sinistra diventa quella più a destra e una catena a sinistra diventa una catena a destra. Invertendolo due volte si ottiene di nuovo l’albero originale.

Qual è la complessità temporale dell'inversione di un albero binario?

Ogni nodo viene visitato una volta, quindi il tempo è O(n). Una soluzione ricorsiva usa O(h) di spazio nello stack per un albero di profondità h, mentre una basata su una coda usa O(w) per il livello più ampio. In questa versione con array, la risposta stessa è un nuovo array, che aggiunge O(n).

Come si inverte un albero binario senza ricorsione?

Usa una coda o una pila. Inizia dalla radice e, ogni volta che estrai un nodo, scambia il figlio sinistro con quello destro e inserisci i figli. Ogni nodo viene scambiato una volta, nell’ordine in cui la struttura te li restituisce. Nella versione con array, accoda invece coppie di indici e scrivi ogni nodo direttamente nella posizione speculare.

Perché invertire un albero binario inverte ogni livello?

Il rispecchiamento inverte sinistra e destra ovunque, quindi i nodi di ogni livello appaiono nell’ordine opposto. Nella memorizzazione in ordine di livello, ciò significa che la porzione dell’array di ogni livello viene invertita: la porzione [1, 4, -1, 9] del primo esempio diventa [9, -1, 4, 1]. Invertire ogni livello, dopo aver aggiunto -1 come riempimento all’ultimo, è una terza soluzione O(n) che funziona solo con questo layout dell’array.

Python

def invertTree(tree):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

tree = [5, 3, 8, 1, 4, -1, 9]

Atteso

[5, 8, 3, 9, -1, 4, 1]