Algoritmo de primera búsqueda en profundidad para verificar si dos árboles de expresión son equivalentes

Un árbol de expresión binaria es un tipo de árbol binario que se utiliza para representar expresiones aritméticas. Cada nodo de un árbol de expresión binaria tiene cero o dos hijos. Los nodos hoja (nodos con 0 hijos) corresponden a operandos (variables), y los nodos internos (nodos con dos hijos) corresponden a operadores. En este problema, solo consideramos el operador ‘+’ (es decir, la suma).

expresión-árbol-binario

Se le dan las raíces de dos árboles de expresión binaria, root1 y root2. Devuelve verdadero si los dos árboles de expresión binaria son equivalentes. De lo contrario, devuelve falso.

Dos árboles de expresión binaria son equivalentes si se evalúan con el mismo valor, independientemente de cómo estén configuradas las variables.

Seguimiento: ¿Qué cambiará en su solución si el árbol también admite el operador ‘-‘ (es decir, resta)?

Ejemplo 1:
Entrada: raíz1 = [x], raíz2 = [x]
Salida: verdadero

Ejemplo 2:
Entrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Salida: verdadero
Explicación: a + (b + c) == (b + c) + un

Ejemplo 3:
Entrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Salida: false
Explicación: a + (b + c) != (b + d) + un

Restricciones:
El número de nodos en ambos árboles es igual, impar y en el rango [1, 4999].
Node.val es ‘+’ o una letra minúscula en inglés.
Se garantiza que el árbol dado es un árbol de expresión binaria válido.

Sugerencias:
Cuente para cada variable cuántas veces apareció en el primer árbol.
Haz lo mismo con el segundo árbol y verifica si el conteo es el mismo para ambos árboles.

Algoritmo de primera búsqueda de profundidad con tabla hash

Dado que el árbol de expresión es binario y solo puede contener un símbolo más. Por lo tanto, podemos realizar el algoritmo de búsqueda primero en profundidad (DFS) en ambos árboles de expresión binaria y contar cada variable. Los dos árboles de expresión son iguales si ambos árboles contienen el mismo número de variables.

El DFS se ejecuta en tiempo O(N), donde N es el número de nodos en ambos árboles de expresión binaria. La complejidad del espacio es O (N) ya que estamos usando la pila a través de la recursividad y también necesitamos registrar los contadores para cada variable.

Para comparar si dos mapas hash son iguales (unordered_map ), simplemente podemos compararlos en C++ usando el doble signo igual.