{"id":233185,"date":"2023-02-07T14:47:00","date_gmt":"2023-02-07T11:47:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233185"},"modified":"2023-02-07T14:48:13","modified_gmt":"2023-02-07T11:48:13","slug":"algoritmo-de-primera-busqueda-en-profundidad-para-verificar-si-dos-arboles-de-expresion-son-equivalentes","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/es\/algoritmo-de-primera-busqueda-en-profundidad-para-verificar-si-dos-arboles-de-expresion-son-equivalentes\/","title":{"rendered":"Algoritmo de primera b\u00fasqueda en profundidad para verificar si dos \u00e1rboles de expresi\u00f3n son equivalentes"},"content":{"rendered":"\n
\n

Un \u00e1rbol de expresi\u00f3n binaria es un tipo de \u00e1rbol binario que se utiliza para representar expresiones aritm\u00e9ticas. Cada nodo de un \u00e1rbol de expresi\u00f3n 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).<\/p>\n

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

expresi\u00f3n-\u00e1rbol-binario<\/p>\n

Se le dan las ra\u00edces de dos \u00e1rboles de expresi\u00f3n binaria, root1 y root2. Devuelve verdadero si los dos \u00e1rboles de expresi\u00f3n binaria son equivalentes. De lo contrario, devuelve falso.<\/p>\n

Dos \u00e1rboles de expresi\u00f3n binaria son equivalentes si se eval\u00faan con el mismo valor, independientemente de c\u00f3mo est\u00e9n configuradas las variables.<\/p>\n

Seguimiento: \u00bfQu\u00e9 cambiar\u00e1 en su soluci\u00f3n si el \u00e1rbol tambi\u00e9n admite el operador ‘-‘ (es decir, resta)?<\/p>\n

Ejemplo 1:
\nEntrada: ra\u00edz1 = [x], ra\u00edz2 = [x]
\nSalida: verdadero<\/p>\n

Ejemplo 2:
\nEntrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nSalida: verdadero
\nExplicaci\u00f3n: a + (b + c) == (b + c) + un<\/p>\n

Ejemplo 3:
\nEntrada: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nSalida: false
\nExplicaci\u00f3n: a + (b + c) != (b + d) + un<\/p>\n

Restricciones:
\nEl n\u00famero de nodos en ambos \u00e1rboles es igual, impar y en el rango [1, 4999].
\nNode.val es ‘+’ o una letra min\u00fascula en ingl\u00e9s.
\nSe garantiza que el \u00e1rbol dado es un \u00e1rbol de expresi\u00f3n binaria v\u00e1lido.<\/p>\n

Sugerencias:
\nCuente para cada variable cu\u00e1ntas veces apareci\u00f3 en el primer \u00e1rbol.
\nHaz lo mismo con el segundo \u00e1rbol y verifica si el conteo es el mismo para ambos \u00e1rboles.<\/p>\n<\/blockquote>\n

Algoritmo de primera b\u00fasqueda de profundidad con tabla hash<\/h3>\n

Dado que el \u00e1rbol de expresi\u00f3n<\/a> es binario y solo puede contener un s\u00edmbolo m\u00e1s. Por lo tanto, podemos realizar el algoritmo de b\u00fasqueda primero en profundidad (DFS) en ambos \u00e1rboles de expresi\u00f3n binaria y contar cada variable. Los dos \u00e1rboles de expresi\u00f3n son iguales si ambos \u00e1rboles contienen el mismo n\u00famero 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
El DFS<\/a> se ejecuta en tiempo O(N), donde N es el n\u00famero de nodos en ambos \u00e1rboles de expresi\u00f3n binaria. La complejidad del espacio es O (N) ya que estamos usando la pila a trav\u00e9s de la recursividad y tambi\u00e9n necesitamos registrar los contadores para cada variable.<\/p>\n
Para comparar si dos mapas hash son iguales (unordered_map<\/a> ), simplemente podemos compararlos en C++ usando el doble signo igual.<\/p>\n
Fuente de grabaci\u00f3n:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Algoritmo de primera b\u00fasqueda en profundidad para verificar si dos \u00e1rboles de expresi\u00f3n son 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":[892,716,747,831,840],"tags":[1172],"class_list":["post-233185","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codigo","category-desarrollador","category-fuente-abierta","category-guia-para-principiantes","category-tutoriales","tag-affiai-es"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts\/233185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/comments?post=233185"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts\/233185\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/media?parent=233185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/categories?post=233185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/tags?post=233185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}