{"id":233232,"date":"2023-02-07T15:18:00","date_gmt":"2023-02-07T12:18:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233232"},"modified":"2023-02-07T15:28:17","modified_gmt":"2023-02-07T12:28:17","slug":"algoritmo-di-ricerca-in-profondita-per-verificare-se-due-alberi-di-espressione-sono-equivalenti","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/it\/algoritmo-di-ricerca-in-profondita-per-verificare-se-due-alberi-di-espressione-sono-equivalenti\/","title":{"rendered":"Algoritmo di ricerca in profondit\u00e0 per verificare se due alberi di espressione sono equivalenti"},"content":{"rendered":"\n
\n

Un albero delle espressioni binarie \u00e8 una specie di albero binario utilizzato per rappresentare le espressioni aritmetiche. Ogni nodo di un albero delle espressioni binario ha zero o due figli. I nodi foglia (nodi con 0 figli) corrispondono agli operandi (variabili) e i nodi interni (nodi con due figli) corrispondono agli operatori. In questo problema, consideriamo solo l’operatore ‘+’ (cio\u00e8 l’addizione).<\/p>\n

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

espressione-albero-binario<\/p>\n

Vengono fornite le radici di due alberi di espressione binari, root1 e root2. Restituisce true se i due alberi delle espressioni binarie sono equivalenti. In caso contrario, restituisci false.<\/p>\n

Due alberi delle espressioni binarie sono equivalenti se valutano lo stesso valore indipendentemente dall’impostazione delle variabili.<\/p>\n

Follow-up: cosa cambierai nella tua soluzione se l’albero supporta anche l’operatore ‘-‘ (es. sottrazione)?<\/p>\n

Esempio 1:
\nInput: root1 = [x], root2 = [x]
\nOutput: true<\/p>\n

Esempio 2:
\nInput: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nOutput: true
\nSpiegazione: a + (b + c) == (b + c) + a<\/p>\n

Esempio 3:
\nInput: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nOutput: false
\nSpiegazione: a + (b + c) != (b + d) + a<\/p>\n

Vincoli:
\nil numero di nodi in entrambi gli alberi \u00e8 uguale, dispari e, nell’intervallo [1, 4999].
\nNode.val \u00e8 ‘+’ o una lettera inglese minuscola.
\n\u00c8 garantito che l’albero fornito sia un albero di espressioni binarie valido.<\/p>\n

Suggerimenti:
\nconta per ogni variabile quante volte \u00e8 apparsa nel primo albero.
\nFai lo stesso per il secondo albero e controlla se il conteggio \u00e8 lo stesso per entrambi gli alberi.<\/p>\n<\/blockquote>\n

Algoritmo di ricerca in profondit\u00e0 con tabella hash<\/h3>\n

Poich\u00e9 l’ albero delle espressioni<\/a> \u00e8 binario e pu\u00f2 contenere solo un simbolo pi\u00f9. Pertanto, possiamo eseguire l’algoritmo di ricerca in profondit\u00e0 (DFS) su entrambi gli alberi delle espressioni binarie e contare ciascuna variabile. I due alberi delle espressioni sono uguali se entrambi gli alberi contengono lo stesso numero di variabili.<\/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
Il DFS<\/a> viene eseguito in tempo O(N) dove N \u00e8 il numero dei nodi in entrambi gli alberi delle espressioni binarie. La complessit\u00e0 dello spazio \u00e8 O(N) poich\u00e9 utilizziamo lo stack tramite ricorsione e dobbiamo anche registrare i contatori per ciascuna variabile.<\/p>\n
Per confrontare se due mappe hash sono uguali (unordered_map<\/a> ), possiamo semplicemente confrontarle in C++ usando il doppio segno di uguale.<\/p>\n
Fonte di registrazione:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Algoritmo di ricerca in profondit\u00e0 per verificare se due alberi di espressione sono equivalenti<\/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":[896,835,751,720,844],"tags":[1168],"class_list":["post-233232","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codice","category-guida-per-principianti","category-open-source-projektmanagement-3","category-sviluppatore","category-tutorial","tag-affiai-it"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts\/233232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/comments?post=233232"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts\/233232\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/media?parent=233232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/categories?post=233232"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/tags?post=233232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}