{"id":233200,"date":"2023-02-07T15:07:00","date_gmt":"2023-02-07T12:07:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233200"},"modified":"2023-02-07T15:08:19","modified_gmt":"2023-02-07T12:08:19","slug":"algorytm-wyszukiwania-glebokosci-w-celu-sprawdzenia-czy-dwa-drzewa-wyrazen-sa-rownowazne","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/pl\/algorytm-wyszukiwania-glebokosci-w-celu-sprawdzenia-czy-dwa-drzewa-wyrazen-sa-rownowazne\/","title":{"rendered":"Algorytm wyszukiwania g\u0142\u0119boko\u015bci w celu sprawdzenia, czy dwa drzewa wyra\u017ce\u0144 s\u0105 r\u00f3wnowa\u017cne"},"content":{"rendered":"\n
\n

Drzewo wyra\u017ce\u0144 binarnych to rodzaj drzewa binarnego u\u017cywanego do reprezentowania wyra\u017ce\u0144 arytmetycznych. Ka\u017cdy w\u0119ze\u0142 drzewa wyra\u017ce\u0144 binarnych ma zero lub dwoje dzieci. W\u0119z\u0142y li\u015bcia (w\u0119z\u0142y z 0 dzie\u0107mi) odpowiadaj\u0105 operandom (zmiennym), a w\u0119z\u0142y wewn\u0119trzne (w\u0119z\u0142y z dw\u00f3jk\u0105 dzieci) odpowiadaj\u0105 operatorom. W tym problemie bierzemy pod uwag\u0119 tylko operator \u201e+" (tj. dodawanie).<\/p>\n

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

wyra\u017cenie-drzewo-binarne<\/p>\n

Otrzymasz korzenie dw\u00f3ch binarnych drzew wyra\u017ce\u0144, root1 i root2. Zwr\u00f3\u0107 warto\u015b\u0107 true, je\u015bli dwa drzewa wyra\u017ce\u0144 binarnych s\u0105 r\u00f3wnowa\u017cne. W przeciwnym razie zwr\u00f3\u0107 fa\u0142sz.<\/p>\n

Dwa drzewa wyra\u017ce\u0144 binarnych s\u0105 r\u00f3wnowa\u017cne, je\u015bli maj\u0105 tak\u0105 sam\u0105 warto\u015b\u0107, niezale\u017cnie od tego, jak ustawione s\u0105 zmienne.<\/p>\n

Kontynuacja: Co zmienisz w swoim rozwi\u0105zaniu, je\u015bli drzewo obs\u0142uguje r\u00f3wnie\u017c operator \u201e-” (tj. odejmowanie)?<\/p>\n

Przyk\u0142ad 1:
\nWej\u015bcie: root1 = [x], root2 = [x]
\nWyj\u015bcie: prawda<\/p>\n

Przyk\u0142ad 2:
\nDane wej\u015bciowe: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a] Dane
\nwyj\u015bciowe: true
\nWyja\u015bnienie: a + (b + c) == (b + c) + a<\/p>\n

Przyk\u0142ad 3:
\nWej\u015bcie: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nWyj\u015bcie: false
\nWyja\u015bnienie: a + (b + c) != (b + d) + a<\/p>\n

Ograniczenia:
\nLiczba w\u0119z\u0142\u00f3w w obu drzewach jest r\u00f3wna, nieparzysta i mie\u015bci si\u0119 w przedziale [1, 4999].
\nNode.val to \u201e+” lub ma\u0142a litera angielska.
\nGwarantujemy, \u017ce podane drzewo jest prawid\u0142owym drzewem wyra\u017ce\u0144 binarnych.<\/p>\n

Wskaz\u00f3wki:
\nPolicz dla ka\u017cdej zmiennej ile razy pojawi\u0142a si\u0119 w pierwszym drzewie.
\nZr\u00f3b to samo dla drugiego drzewa i sprawd\u017a, czy liczba jest taka sama dla obu drzew.<\/p>\n<\/blockquote>\n

Algorytm pierwszego wyszukiwania g\u0142\u0119boko\u015bci z tablic\u0105 mieszaj\u0105c\u0105<\/h3>\n

Poniewa\u017c drzewo wyra\u017ce\u0144<\/a> jest binarne i mo\u017ce zawiera\u0107 tylko jeden symbol plusa. Dlatego mo\u017cemy wykona\u0107 algorytm pierwszego wyszukiwania g\u0142\u0119boko\u015bci (DFS) na obu drzewach wyra\u017ce\u0144 binarnych i policzy\u0107 ka\u017cd\u0105 zmienn\u0105. Dwa drzewa wyra\u017ce\u0144 s\u0105 r\u00f3wne, je\u015bli oba drzewa zawieraj\u0105 tak\u0105 sam\u0105 liczb\u0119 zmiennych.<\/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
System plik\u00f3w DFS<\/a> dzia\u0142a w czasie O(N), gdzie N jest liczb\u0105 w\u0119z\u0142\u00f3w w obu drzewach wyra\u017ce\u0144 binarnych. Z\u0142o\u017cono\u015b\u0107 przestrzeni wynosi O(N), poniewa\u017c u\u017cywamy stosu za pomoc\u0105 rekurencji, a tak\u017ce musimy rejestrowa\u0107 liczniki dla ka\u017cdej zmiennej.<\/p>\n
Aby por\u00f3wna\u0107, czy dwa hash map s\u0105 r\u00f3wne (unordered_map<\/a> ), mo\u017cemy je po prostu por\u00f3wna\u0107 w C++ za pomoc\u0105 podw\u00f3jnego znaku r\u00f3wno\u015bci.<\/p>\n
\u0179r\u00f3d\u0142o nagrywania:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Algorytm wyszukiwania g\u0142\u0119boko\u015bci w celu sprawdzenia, czy dwa drzewa wyra\u017ce\u0144 s\u0105 r\u00f3wnowa\u017cne<\/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":[721,897,752,836,845],"tags":[1169],"class_list":["post-233200","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-deweloper","category-kod","category-otwarte-zrodlo","category-przewodnik-dla-poczatkujacych","category-samouczki","tag-affiai-pl"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/233200","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/comments?post=233200"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/233200\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media?parent=233200"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/categories?post=233200"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/tags?post=233200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}