{"id":233196,"date":"2023-02-07T15:09:00","date_gmt":"2023-02-07T12:09:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233196"},"modified":"2023-02-07T15:13:14","modified_gmt":"2023-02-07T12:13:14","slug":"algoritmo-de-pesquisa-em-profundidade-para-verificar-se-duas-arvores-de-expressao-sao-equivalentes","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/pt-pt\/algoritmo-de-pesquisa-em-profundidade-para-verificar-se-duas-arvores-de-expressao-sao-equivalentes\/","title":{"rendered":"Algoritmo de pesquisa em profundidade para verificar se duas \u00e1rvores de express\u00e3o s\u00e3o equivalentes"},"content":{"rendered":"\n
\n

Uma \u00e1rvore de express\u00e3o bin\u00e1ria \u00e9 um tipo de \u00e1rvore bin\u00e1ria usada para representar express\u00f5es aritm\u00e9ticas. Cada n\u00f3 de uma \u00e1rvore de express\u00e3o bin\u00e1ria tem zero ou dois filhos. Os n\u00f3s folha (n\u00f3s com 0 filhos) correspondem aos operandos (vari\u00e1veis), e os n\u00f3s internos (n\u00f3s com dois filhos) correspondem aos operadores. Neste problema, consideramos apenas o operador ‘+’ (ou seja, adi\u00e7\u00e3o).<\/p>\n

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

express\u00e3o-\u00e1rvore-bin\u00e1ria<\/p>\n

Voc\u00ea recebe as ra\u00edzes de duas \u00e1rvores de express\u00e3o bin\u00e1ria, root1 e root2. Retorna true se as duas \u00e1rvores de express\u00e3o bin\u00e1ria forem equivalentes. Caso contr\u00e1rio, retorne falso.<\/p>\n

Duas \u00e1rvores de express\u00e3o bin\u00e1ria s\u00e3o equivalentes se forem avaliadas com o mesmo valor, independentemente de como as vari\u00e1veis \u200b\u200best\u00e3o definidas.<\/p>\n

Acompanhamento: O que voc\u00ea mudar\u00e1 em sua solu\u00e7\u00e3o se a \u00e1rvore tamb\u00e9m suportar o operador ‘-‘ (ou seja, subtra\u00e7\u00e3o)?<\/p>\n

Exemplo 1:
\nEntrada: root1 = [x], root2 = [x]
\nSa\u00edda: true<\/p>\n

Exemplo 2:
\nEntrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nSa\u00edda: true
\nExplica\u00e7\u00e3o: a + (b + c) == (b + c) + a<\/p>\n

Exemplo 3:
\nEntrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nSa\u00edda: false
\nExplica\u00e7\u00e3o: a + (b + c) != (b + d) + a<\/p>\n

Restri\u00e7\u00f5es:
\nO n\u00famero de n\u00f3s em ambas as \u00e1rvores \u00e9 igual, \u00edmpar e, no intervalo [1, 4999].
\nNode.val \u00e9 ‘+’ ou uma letra min\u00fascula em ingl\u00eas.
\n\u00c9 garantido que a \u00e1rvore fornecida \u00e9 uma \u00e1rvore de express\u00e3o bin\u00e1ria v\u00e1lida.<\/p>\n

Dicas:
\nConte para cada vari\u00e1vel quantas vezes ela apareceu na primeira \u00e1rvore.
\nFa\u00e7a o mesmo para a segunda \u00e1rvore e verifique se a contagem \u00e9 a mesma para ambas as \u00e1rvores.<\/p>\n<\/blockquote>\n

Algoritmo de primeira pesquisa de profundidade com tabela de hash<\/h3>\n

Como a \u00e1rvore de express\u00e3o<\/a> \u00e9 bin\u00e1ria e pode conter apenas um s\u00edmbolo de mais. Portanto, podemos executar o algoritmo Depth First Search (DFS) em ambas as \u00e1rvores de express\u00e3o bin\u00e1ria e contar cada vari\u00e1vel. As duas \u00e1rvores de express\u00e3o s\u00e3o iguais se ambas as \u00e1rvores contiverem o mesmo n\u00famero de vari\u00e1veis.<\/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
O DFS<\/a> \u00e9 executado em tempo O(N), onde N \u00e9 o n\u00famero de n\u00f3s em ambas as \u00e1rvores de express\u00e3o bin\u00e1ria. A complexidade do espa\u00e7o \u00e9 O(N), pois estamos usando pilha via recurs\u00e3o e tamb\u00e9m precisamos registrar os contadores para cada vari\u00e1vel.<\/p>\n
Para comparar se dois mapas de hash s\u00e3o iguais (unordered_map<\/a> ), podemos simplesmente compar\u00e1-los em C++ usando o sinal de igual duplo.<\/p>\n
Fonte de grava\u00e7\u00e3o:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Algoritmo de pesquisa em profundidade para verificar se duas \u00e1rvores de express\u00e3o s\u00e3o equivalentes<\/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":[898,753,722,837,846],"tags":[1170],"class_list":["post-233196","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codigo-2","category-codigo-aberto","category-desenvolvedor","category-guia-para-iniciantes","category-tutoriais","tag-affiai-pt-pt"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts\/233196","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/comments?post=233196"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts\/233196\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/media?parent=233196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/categories?post=233196"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/tags?post=233196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}