Algorithme de recherche en profondeur pour vérifier si deux arbres d’expression sont équivalents

Un arbre d’expression binaire est une sorte d’arbre binaire utilisé pour représenter des expressions arithmétiques. Chaque nœud d’un arbre d’expression binaire a zéro ou deux enfants. Les nœuds feuilles (nœuds avec 0 enfant) correspondent aux opérandes (variables), et les nœuds internes (nœuds avec deux enfants) correspondent aux opérateurs. Dans ce problème, nous ne considérons que l’opérateur ‘+’ (c’est-à-dire l’addition).

expression-arbre-binaire

On vous donne les racines de deux arbres d’expressions binaires, root1 et root2. Renvoie true si les deux arborescences d’expressions binaires sont équivalentes. Sinon, renvoie faux.

Deux arborescences d’expressions binaires sont équivalentes si elles donnent la même valeur, quelle que soit la valeur des variables.

Suivi : qu’allez-vous changer dans votre solution si l’arbre prend également en charge l’opérateur "-" (c’est-à-dire la soustraction) ?

Exemple 1 :
Entrée: racine1 = [x], racine2 = [x]
Sortie: vrai

Exemple 2 :
Entrée: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Sortie: true
Explication: a + (b + c) == (b + c) + un

Exemple 3 :
Entrée: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Sortie: false
Explication: a + (b + c) != (b + d) + une

Contraintes :
Le nombre de nœuds dans les deux arbres est égal, impair et, dans l’intervalle [1, 4999].
Node.val est ‘+’ ou une lettre anglaise minuscule.
Il est garanti que l’arbre donné est un arbre d’expression binaire valide.

Conseils :
Comptez pour chaque variable combien de fois elle est apparue dans le premier arbre.
Faites de même pour le deuxième arbre et vérifiez si le nombre est le même pour les deux arbres.

Algorithme de recherche en profondeur avec table de hachage

Étant donné que l’ arbre d’ expression est binaire et ne peut contenir qu’un seul symbole plus. Par conséquent, nous pouvons effectuer l’algorithme de recherche en profondeur (DFS) sur les deux arbres d’expression binaires et compter chaque variable. Les deux arbres d’expression sont égaux si les deux arbres contiennent le même nombre de variables.

Le DFS s’exécute en temps O (N) où N est le nombre de nœuds dans les deux arbres d’expression binaires. La complexité spatiale est O (N) car nous utilisons la pile via la récursivité et devons également enregistrer les compteurs pour chaque variable.

Pour comparer si deux cartes de hachage sont égales (unordered_map ), nous pouvons simplement les comparer en C++ en utilisant le double signe égal.