Algoritmo di ricerca in profondità per verificare se due alberi di espressione sono equivalenti

Un albero delle espressioni binarie è una specie di albero binario utilizzato per rappresentare le espressioni aritmetiche. Ogni nodo di un albero delle espressioni binario ha zero o due figli. I nodi foglia (nodi con 0 figli) corrispondono agli operandi (variabili) e i nodi interni (nodi con due figli) corrispondono agli operatori. In questo problema, consideriamo solo l’operatore ‘+’ (cioè l’addizione).

espressione-albero-binario

Vengono fornite le radici di due alberi di espressione binari, root1 e root2. Restituisce true se i due alberi delle espressioni binarie sono equivalenti. In caso contrario, restituisci false.

Due alberi delle espressioni binarie sono equivalenti se valutano lo stesso valore indipendentemente dall’impostazione delle variabili.

Follow-up: cosa cambierai nella tua soluzione se l’albero supporta anche l’operatore ‘-‘ (es. sottrazione)?

Esempio 1:
Input: root1 = [x], root2 = [x]
Output: true

Esempio 2:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Output: true
Spiegazione: a + (b + c) == (b + c) + a

Esempio 3:
Input: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Output: false
Spiegazione: a + (b + c) != (b + d) + a

Vincoli:
il numero di nodi in entrambi gli alberi è uguale, dispari e, nell’intervallo [1, 4999].
Node.val è ‘+’ o una lettera inglese minuscola.
È garantito che l’albero fornito sia un albero di espressioni binarie valido.

Suggerimenti:
conta per ogni variabile quante volte è apparsa nel primo albero.
Fai lo stesso per il secondo albero e controlla se il conteggio è lo stesso per entrambi gli alberi.

Algoritmo di ricerca in profondità con tabella hash

Poiché l’ albero delle espressioni è binario e può contenere solo un simbolo più. Pertanto, possiamo eseguire l’algoritmo di ricerca in profondità (DFS) su entrambi gli alberi delle espressioni binarie e contare ciascuna variabile. I due alberi delle espressioni sono uguali se entrambi gli alberi contengono lo stesso numero di variabili.

Il DFS viene eseguito in tempo O(N) dove N è il numero dei nodi in entrambi gli alberi delle espressioni binarie. La complessità dello spazio è O(N) poiché utilizziamo lo stack tramite ricorsione e dobbiamo anche registrare i contatori per ciascuna variabile.

Per confrontare se due mappe hash sono uguali (unordered_map ), possiamo semplicemente confrontarle in C++ usando il doppio segno di uguale.