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.

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.