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.

/**
 * Definition for a binary tree node.
 * struct Node {
 *     char val;
 *     Node *left;
 *     Node *right;
 *     Node(): val(' '), left(nullptr), right(nullptr) {}
 *     Node(char x): val(x), left(nullptr), right(nullptr) {}
 *     Node(char x, Node *left, Node *right): val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checkEquivalence(Node* root1, Node* root2) {
        if (root1 == root2) return true;
        unordered_map<char, int> count1, count2;
        dfs(root1, count1);
        dfs(root2, count2);
        return count1 == count2;
    }
    
private:        
    void dfs(Node* root, unordered_map<char, int> &count) {
        if (!root) return ;
        if (root->val != '+') count[root->val] ++;
        dfs(root->left, count);
        dfs(root->right, count);
    }
};

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.