{"id":234183,"date":"2023-02-07T15:09:00","date_gmt":"2023-02-07T12:09:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=234183"},"modified":"2023-02-07T15:13:23","modified_gmt":"2023-02-07T12:13:23","slug":"algorithme-de-recherche-en-profondeur-pour-verifier-si-deux-arbres-dexpression-sont-equivalents","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/fr\/algorithme-de-recherche-en-profondeur-pour-verifier-si-deux-arbres-dexpression-sont-equivalents\/","title":{"rendered":"Algorithme de recherche en profondeur pour v\u00e9rifier si deux arbres d’expression sont \u00e9quivalents"},"content":{"rendered":"\n
\n

Un arbre d’expression binaire est une sorte d’arbre binaire utilis\u00e9 pour repr\u00e9senter des expressions arithm\u00e9tiques. Chaque n\u0153ud d’un arbre d’expression binaire a z\u00e9ro ou deux enfants. Les n\u0153uds feuilles (n\u0153uds avec 0 enfant) correspondent aux op\u00e9randes (variables), et les n\u0153uds internes (n\u0153uds avec deux enfants) correspondent aux op\u00e9rateurs. Dans ce probl\u00e8me, nous ne consid\u00e9rons que l’op\u00e9rateur ‘+’ (c’est-\u00e0-dire l’addition).<\/p>\n

\"Algorithme<\/a><\/p>\n

expression-arbre-binaire<\/p>\n

On vous donne les racines de deux arbres d’expressions binaires, root1 et root2. Renvoie true si les deux arborescences d’expressions binaires sont \u00e9quivalentes. Sinon, renvoie faux.<\/p>\n

Deux arborescences d’expressions binaires sont \u00e9quivalentes si elles donnent la m\u00eame valeur, quelle que soit la valeur des variables.<\/p>\n

Suivi\u00a0: qu’allez-vous changer dans votre solution si l’arbre prend \u00e9galement en charge l’op\u00e9rateur "-" (c’est-\u00e0-dire la soustraction)\u00a0?<\/p>\n

Exemple 1 :
\nEntr\u00e9e: racine1 = [x], racine2 = [x]
\nSortie: vrai<\/p>\n

Exemple 2 :
\nEntr\u00e9e: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nSortie: true
\nExplication: a + (b + c) == (b + c) + un<\/p>\n

Exemple 3 :
\nEntr\u00e9e: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nSortie: false
\nExplication: a + (b + c) != (b + d) + une<\/p>\n

Contraintes :
\nLe nombre de n\u0153uds dans les deux arbres est \u00e9gal, impair et, dans l’intervalle [1, 4999].
\nNode.val est ‘+’ ou une lettre anglaise minuscule.
\nIl est garanti que l’arbre donn\u00e9 est un arbre d’expression binaire valide.<\/p>\n

Conseils :
\nComptez pour chaque variable combien de fois elle est apparue dans le premier arbre.
\nFaites de m\u00eame pour le deuxi\u00e8me arbre et v\u00e9rifiez si le nombre est le m\u00eame pour les deux arbres.<\/p>\n<\/blockquote>\n

Algorithme de recherche en profondeur avec table de hachage<\/h3>\n

\u00c9tant donn\u00e9 que l’ arbre d’ expression<\/a> est binaire et ne peut contenir qu’un seul symbole plus. Par cons\u00e9quent, 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 \u00e9gaux si les deux arbres contiennent le m\u00eame nombre de variables.<\/p>\n

\/**\n\u00a0* Definition for a binary tree node.\n\u00a0* struct Node {\n\u00a0* \u00a0 \u00a0 char val;\n\u00a0* \u00a0 \u00a0 Node *left;\n\u00a0* \u00a0 \u00a0 Node *right;\n\u00a0* \u00a0 \u00a0 Node(): val(' '), left(nullptr), right(nullptr) {}\n\u00a0* \u00a0 \u00a0 Node(char x): val(x), left(nullptr), right(nullptr) {}\n\u00a0* \u00a0 \u00a0 Node(char x, Node *left, Node *right): val(x), left(left), right(right) {}\n\u00a0* };\n\u00a0*\/\nclass Solution {\npublic:\n\u00a0 \u00a0 bool checkEquivalence(Node* root1, Node* root2) {\n\u00a0 \u00a0 \u00a0 \u00a0 if (root1 == root2) return true;\n\u00a0 \u00a0 \u00a0 \u00a0 unordered_map<char, int> count1, count2;\n\u00a0 \u00a0 \u00a0 \u00a0 dfs(root1, count1);\n\u00a0 \u00a0 \u00a0 \u00a0 dfs(root2, count2);\n\u00a0 \u00a0 \u00a0 \u00a0 return count1 == count2;\n\u00a0 \u00a0 }\n\u00a0 \u00a0 \nprivate: \u00a0 \u00a0 \u00a0 \u00a0\n\u00a0 \u00a0 void dfs(Node* root, unordered_map<char, int> &count) {\n\u00a0 \u00a0 \u00a0 \u00a0 if (!root) return ;\n\u00a0 \u00a0 \u00a0 \u00a0 if (root->val != '+') count[root->val] ++;\n\u00a0 \u00a0 \u00a0 \u00a0 dfs(root->left, count);\n\u00a0 \u00a0 \u00a0 \u00a0 dfs(root->right, count);\n\u00a0 \u00a0 }\n};<\/code><\/pre>\n
Le DFS<\/a> s’ex\u00e9cute en temps O (N) o\u00f9 N est le nombre de n\u0153uds dans les deux arbres d’expression binaires. La complexit\u00e9 spatiale est O (N) car nous utilisons la pile via la r\u00e9cursivit\u00e9 et devons \u00e9galement enregistrer les compteurs pour chaque variable.<\/p>\n
Pour comparer si deux cartes de hachage sont \u00e9gales (unordered_map<\/a> ), nous pouvons simplement les comparer en C++ en utilisant le double signe \u00e9gal.<\/p>\n
Source d’enregistrement:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Algorithme de recherche en profondeur pour v\u00e9rifier si deux arbres d’expression sont \u00e9quivalents<\/p>\n","protected":false},"author":1,"featured_media":224845,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_wp_rev_ctl_limit":""},"categories":[893,717,832,748,841],"tags":[1167],"class_list":["post-234183","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-code-2","category-developpeur","category-guide-pour-les-debutants","category-open-source-projektmanagement-2","category-tutoriels","tag-affiai-fr"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts\/234183","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/comments?post=234183"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts\/234183\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/media?parent=234183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/categories?post=234183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/tags?post=234183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}