Symmetric Tree

Q: Qual è la complessità temporale dell’albero simmetrico?

Ogni nodo reale viene confrontato una volta, come parte di una coppia speculare, quindi il tempo è O(n) . Le versioni ricorsiva e con stack usano O(h) di spazio aggiuntivo per le coppie in sospeso lungo il percorso corrente. La versione livello per livello mantiene in memoria un livello, O(w) per il livello più ampio.

Q: Come si verifica se un albero binario è simmetrico senza ricorsione?

Mantieni una pila o una coda di coppie di nodi che devono rispecchiarsi, iniziando dai due figli della radice. Estrai una coppia, restituisci un errore in caso di mancata corrispondenza e aggiungi la coppia esterna e quella interna dei loro figli. Se la pila si svuota senza che ci siano mancate corrispondenze, l’albero è simmetrico.

Q: Qual è la differenza tra un albero simmetrico e due alberi identici?

Due alberi sono identici quando confronti il sinistro con il sinistro e il destro con il destro. Un albero è simmetrico quando il suo sottoalbero sinistro è identico all’immagine speculare del suo sottoalbero destro, quindi il confronto incrocia i rami: il sinistro con il destro e il destro con il sinistro. Lo stesso codice di verifica delle coppie risolve entrambi i problemi scambiando le coppie di figli.

Q: Un albero con un solo nodo è simmetrico?

Sì. Un singolo nodo ha due posizioni vuote per i figli, e due posizioni vuote si rispecchiano a vicenda. Una radice con esattamente un figlio non è mai simmetrica, perché quel figlio si trova di fronte a una posizione vuota.

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 ulteriori voci -1. Restituisci true se l’albero è simmetrico rispetto a una linea verticale che passa per la radice e false altrimenti. Devono corrispondere sia la struttura sia i valori.

Funzione

isSymmetric(tree: integer-array) → boolean

treeinteger-array: l’albero binario in ordine per livelli, con -1 per una posizione vuota
Restituisceboolean: vero se l'albero è speculare, falso altrimenti

Vincoli

1 ≤ tree.length ≤ 32767
Ogni tree[i] è -1 oppure un valore con 0 ≤ tree[i] ≤ 1000.
tree[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 una posizione vuota sono vuoti a loro volta, e la profondità è al massimo 14.

Esempi

Input: tree = [1, 2, 2, 3, 4, 4, 3]
Output: true
Spiegazione: Piega l'albero a metà. I due 2 agli indici 1 e 2 si incontrano, i 3 esterni agli indici 3 e 6 si incontrano e i 4 interni agli indici 4 e 5 si incontrano.

Input: tree = [1, 2, 2, -1, 3, -1, 3]
Output: false
Spiegazione: Entrambi i 3 pendono a destra dei rispettivi genitori. In un'immagine speculare, il figlio destro del 2 sinistro (indice 4) deve essere rivolto verso il figlio sinistro del 2 destro (indice 5), e l'indice 5 è vuoto.

Input: tree = [4, 6, 6, 5, -1, -1, 9]
Output: false
Spiegazione: La forma è un'immagine speculare: l'indice 3 è di fronte all'indice 6 ed entrambi contengono un nodo. I loro valori sono diversi, 5 contro 9, quindi l'albero non è simmetrico.

+16 test nascosti all’invio

Per approfondire

Se la forma è speculare ma alcuni valori non lo sono, qual è il numero minimo di valori dei nodi da modificare per rendere l’albero simmetrico?

Suggerimenti

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

0 di 3 aperti

Soluzione

La simmetria è una proprietà delle coppie. Ogni nodo ha un partner nel punto speculare dall’altro lato della radice, e il partner di un figlio sinistro è un figlio destro. Quindi non confronti mai un nodo con i suoi stessi figli: percorri contemporaneamente le due metà dell’albero in direzioni opposte, confronti forma e valore di ogni coppia e ti fermi alla prima coppia che non corrisponde.

Confronta ogni livello con il suo inverso

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 è reale solo se il suo indice è all’interno dell’array e il valore corrispondente non è -1. In [1, 2, 2, 3, 4, 4, 3], la radice 1 ha i figli agli indici 1 e 2, e il 2 all’indice 1 ha i figli agli indici 3 e 4.

Ora osserva l’albero un livello alla volta. Un’immagine speculare si legge allo stesso modo da sinistra a destra e da destra a sinistra, quindi ogni livello, scritto includendo gli spazi vuoti, deve leggersi allo stesso modo in entrambe le direzioni. Nel primo esempio, i livelli sotto la radice sono 2 2 e 3 4 4 3. Nel secondo sono 2 2 e poi -1 3 -1 3, che invertito diventa 3 -1 3 -1, quindi la risposta è false.

Gli spazi vuoti devono restare nella sequenza. Senza di essi, il livello inferiore del secondo esempio sarebbe 3 3 e risulterebbe valido. Scrivi una voce per ogni posizione dei figli di ciascun nodo reale del livello, -1 per una posizione vuota; anche i figli delle posizioni vuote sono vuoti, quindi non aggiungono nulla. Ogni nodo viene visitato una volta, quindi il tempo è O(n), e in memoria viene mantenuto un solo livello alla volta: O(w) per il livello più ampio w.

Algoritmo

Inizia con una lista che contiene l'indice della radice 0.
Per ogni indice nella lista, da sinistra a destra, annota entrambi i posti dei figli: il valore del figlio se esiste, -1 se è vuoto. Raccogli i figli esistenti per il livello successivo.
Se quella riga di posti dei figli differisce dalla sua versione al contrario, restituisci false.
Passa al livello successivo e ripeti finché non è vuoto, poi restituisci true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Ricorsione su coppie speculari

Intuizione

Invece di confrontare livelli interi, confronta due sottoalberi: quello sinistro della radice, che inizia all'indice 1, e quello destro, che inizia all'indice 2. Due posizioni sono speculari quando sono entrambe vuote oppure quando contengono lo stesso valore e i loro figli si incrociano. Il figlio sinistro di una corrisponde al figlio destro dell'altra (la coppia esterna) e il figlio destro di una corrisponde al figlio sinistro dell'altra (la coppia interna).

Nel primo esempio, mirrors(1, 2) confronta i due 2, poi chiama mirrors(3, 6) per i 3 esterni e mirrors(4, 5) per i 4 interni. Ognuna di queste chiamate trova solo posizioni vuote al di sotto e restituisce true. Nel secondo esempio, mirrors(4, 5) trova un 3 all'indice 4 di fronte a una posizione vuota all'indice 5, restituisce false e il false risale fino alla radice.

Ogni nodo reale appartiene al massimo a una coppia, quindi il tempo è O(n). Lo stack delle chiamate è profondo quanto l'albero, O(h), che in questo caso è al massimo di 14 frame.

Algoritmo

Scrivi mirrors(a, b). Una posizione è vuota quando il suo indice supera la fine o contiene -1. Se entrambe le posizioni sono vuote, restituisci true; se lo è solo una, restituisci false.
Se tree[a] e tree[b] sono diversi, restituisci false.
Altrimenti restituisci mirrors(2*a+1, 2*b+2) e mirrors(2*a+2, 2*b+1).
Restituisci mirrors(1, 2). Una radice senza figli corrisponde a due posizioni vuote, quindi il risultato è true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Stack esplicito di coppie speculari

Intuizione

La ricorsione richiede una sola cosa: le coppie ancora in attesa di essere controllate. Tieni queste coppie su uno stack gestito da te e le chiamate scompaiono. Inizia con la coppia (1, 2). Estrai una coppia. Se entrambe le posizioni sono vuote, non c’è nulla sotto di esse, quindi vai avanti. Se una è vuota o i valori differiscono, l’albero non è simmetrico. Altrimenti inserisci la coppia esterna (2*a+1, 2*b+2) e la coppia interna (2*a+2, 2*b+1).

L’ordine in cui controlli le coppie non ha importanza, perché l’albero è simmetrico solo se ogni coppia corrisponde. Uno stack segue l’ordine in profondità; una coda seguirebbe l’ordine per livelli e funzionerebbe allo stesso modo. Il terzo esempio si ferma alla prima coppia non corrispondente, (3, 6), che contiene 5 e 9.

Ogni estrazione gestisce una coppia e ogni nodo effettivo fa parte al massimo di una coppia, quindi il tempo è O(n). Lo stack conserva circa una coppia in sospeso per livello del percorso corrente, con spazio O(h), e non c’è alcun limite di ricorsione di cui preoccuparsi.

Algoritmo

Inserisci la coppia (1, 2) in uno stack.
Estrai una coppia (a, b). Se entrambe le posizioni sono vuote (indice oltre la fine o -1), passa alla coppia successiva.
Se solo una posizione è vuota, oppure tree[a] è diverso da tree[b], restituisci false.
Inserisci (2*a+1, 2*b+2) e (2*a+2, 2*b+1).
Quando lo stack è vuoto, restituisci true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Trappole e casi limite

La maggior parte delle risposte sbagliate confronta la coppia di nodi errata oppure dimentica che una posizione vuota fa parte della struttura.

Controllare ogni sottoalbero da solo. Il sottoalbero sinistro non deve essere simmetrico di per sé: in [1, 2, 2, 3, 4, 4, 3] il sottoalbero 2, 3, 4 non lo è, mentre l’albero intero sì. Deve essere speculare al sottoalbero destro.
Abbinare i figli nel modo sbagliato. Il figlio sinistro di un lato corrisponde al figlio destro dell’altro: (2*a+1, 2*b+2) e (2*a+2, 2*b+1), mai (2*a+1, 2*b+1).
Confrontare solo i valori. Se rimuovi le posizioni vuote da [1, 2, 2, -1, 3, -1, 3], ogni livello risulta uguale nei due sensi, eppure l’albero non è simmetrico. Mantieni -1 nella riga del livello oppure controlla che le posizioni siano vuote nel test delle coppie.
Leggere oltre la fine. Un indice oltre la fine dell’array corrisponde a una posizione vuota. Controlla a < n prima di leggere tree[a]; un albero con un solo nodo non ha affatto gli indici 1 o 2.
Fermarsi alla prima coppia corrispondente. Una singola coppia corretta non dimostra nulla; restituisci true solo dopo aver controllato ogni coppia.
Confondere l’offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

Qual è la complessità temporale dell’albero simmetrico?

Ogni nodo reale viene confrontato una volta, come parte di una coppia speculare, quindi il tempo è O(n). Le versioni ricorsiva e con stack usano O(h) di spazio aggiuntivo per le coppie in sospeso lungo il percorso corrente. La versione livello per livello mantiene in memoria un livello, O(w) per il livello più ampio.

Come si verifica se un albero binario è simmetrico senza ricorsione?

Mantieni una pila o una coda di coppie di nodi che devono rispecchiarsi, iniziando dai due figli della radice. Estrai una coppia, restituisci un errore in caso di mancata corrispondenza e aggiungi la coppia esterna e quella interna dei loro figli. Se la pila si svuota senza che ci siano mancate corrispondenze, l’albero è simmetrico.

Qual è la differenza tra un albero simmetrico e due alberi identici?

Due alberi sono identici quando confronti il sinistro con il sinistro e il destro con il destro. Un albero è simmetrico quando il suo sottoalbero sinistro è identico all’immagine speculare del suo sottoalbero destro, quindi il confronto incrocia i rami: il sinistro con il destro e il destro con il sinistro. Lo stesso codice di verifica delle coppie risolve entrambi i problemi scambiando le coppie di figli.

Un albero con un solo nodo è simmetrico?

Sì. Un singolo nodo ha due posizioni vuote per i figli, e due posizioni vuote si rispecchiano a vicenda. Una radice con esattamente un figlio non è mai simmetrica, perché quel figlio si trova di fronte a una posizione vuota.

Python

def isSymmetric(tree):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

tree = [1, 2, 2, 3, 4, 4, 3]

Atteso

true

Symmetric Tree

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Confronta ogni livello con il suo inverso

Ricorsione su coppie speculari

Stack esplicito di coppie speculari

Trappole e casi limite

Domande frequenti4

Problemi simili