Algoritmo de pesquisa em profundidade para verificar se duas árvores de expressão são equivalentes

Uma árvore de expressão binária é um tipo de árvore binária usada para representar expressões aritméticas. Cada nó de uma árvore de expressão binária tem zero ou dois filhos. Os nós folha (nós com 0 filhos) correspondem aos operandos (variáveis), e os nós internos (nós com dois filhos) correspondem aos operadores. Neste problema, consideramos apenas o operador ‘+’ (ou seja, adição).

expressão-árvore-binária

Você recebe as raízes de duas árvores de expressão binária, root1 e root2. Retorna true se as duas árvores de expressão binária forem equivalentes. Caso contrário, retorne falso.

Duas árvores de expressão binária são equivalentes se forem avaliadas com o mesmo valor, independentemente de como as variáveis ​​estão definidas.

Acompanhamento: O que você mudará em sua solução se a árvore também suportar o operador ‘-‘ (ou seja, subtração)?

Exemplo 1:
Entrada: root1 = [x], root2 = [x]
Saída: true

Exemplo 2:
Entrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Saída: true
Explicação: a + (b + c) == (b + c) + a

Exemplo 3:
Entrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Saída: false
Explicação: a + (b + c) != (b + d) + a

Restrições:
O número de nós em ambas as árvores é igual, ímpar e, no intervalo [1, 4999].
Node.val é ‘+’ ou uma letra minúscula em inglês.
É garantido que a árvore fornecida é uma árvore de expressão binária válida.

Dicas:
Conte para cada variável quantas vezes ela apareceu na primeira árvore.
Faça o mesmo para a segunda árvore e verifique se a contagem é a mesma para ambas as árvores.

Algoritmo de primeira pesquisa de profundidade com tabela de hash

Como a árvore de expressão é binária e pode conter apenas um símbolo de mais. Portanto, podemos executar o algoritmo Depth First Search (DFS) em ambas as árvores de expressão binária e contar cada variável. As duas árvores de expressão são iguais se ambas as árvores contiverem o mesmo número de variáveis.

/**
 * 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);
    }
};

O DFS é executado em tempo O(N), onde N é o número de nós em ambas as árvores de expressão binária. A complexidade do espaço é O(N), pois estamos usando pilha via recursão e também precisamos registrar os contadores para cada variável.

Para comparar se dois mapas de hash são iguais (unordered_map ), podemos simplesmente compará-los em C++ usando o sinal de igual duplo.