{"id":233204,"date":"2023-02-07T15:09:00","date_gmt":"2023-02-07T12:09:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233204"},"modified":"2023-02-07T15:13:19","modified_gmt":"2023-02-07T12:13:19","slug":"esimese-suegavuse-otsingu-algoritm-et-kontrollida-kas-kaks-vaeljendipuud-on-samavaeaersed","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/et\/esimese-suegavuse-otsingu-algoritm-et-kontrollida-kas-kaks-vaeljendipuud-on-samavaeaersed\/","title":{"rendered":"Esimese s\u00fcgavuse otsingu algoritm, et kontrollida, kas kaks v\u00e4ljendipuud on samav\u00e4\u00e4rsed"},"content":{"rendered":"\n
\n

Binaaravaldiste puu on teatud t\u00fc\u00fcpi binaarpuu, mida kasutatakse aritmeetiliste avaldiste esitamiseks. Igal binaarse avaldisepuu s\u00f5lmel on kas null v\u00f5i kaks alampunkti. Lehes\u00f5lmed (0 lapsega s\u00f5lmed) vastavad operandidele (muutujatele) ja sisemised s\u00f5lmed (kahe lapsega s\u00f5lmed) vastavad operaatoritele. Selles \u00fclesandes k\u00e4sitleme ainult operaatorit ‘+’ (st liitmist).<\/p>\n

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

v\u00e4ljend-kaks-puu<\/p>\n

Teile antakse kahe binaarse avaldisepuu juured, root1 ja root2. Tagastab t\u00f5ene, kui kaks binaarset avaldisepuud on samav\u00e4\u00e4rsed. Vastasel juhul tagastage vale.<\/p>\n

Kaks binaarset avaldisepuud on samav\u00e4\u00e4rsed, kui nende v\u00e4\u00e4rtus on sama, olenemata muutujate seadistamisest.<\/p>\n

J\u00e4reltegevus: Mida muudate oma lahenduses, kui puu toetab ka operaatorit ‘-‘ (st lahutamist)?<\/p>\n

N\u00e4ide 1:
\nSisend: root1 = [x], root2 = [x]
\nV\u00e4ljund: t\u00f5ene<\/p>\n

N\u00e4ide 2:
\nsisend: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nV\u00e4ljund: t\u00f5ene
\nSelgitus: a + (b + c) == (b + c) + a<\/p>\n

N\u00e4ide 3:
\nSisend: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nV\u00e4ljund: vale
\nSelgitus: a + (b + c) != (b + d) + a<\/p>\n

Piirangud:
\nm\u00f5lema puu s\u00f5lmede arv on v\u00f5rdne, paaritu ja vahemikus [1, 4999].
\nNode.val on ‘+’ v\u00f5i ingliskeelne v\u00e4iket\u00e4ht.
\nOn garanteeritud, et antud puu on kehtiv binaaravaldise puu.<\/p>\n

Vihjed:
\nloendage iga muutuja puhul, mitu korda see esimeses puus esines.
\nTehke sama teise puuga ja kontrollige, kas m\u00f5lema puu arv on sama.<\/p>\n<\/blockquote>\n

Esimese s\u00fcgavuse otsingu algoritm r\u00e4sitabeliga<\/h3>\n

Kuna avaldisepuu<\/a> on binaarne ja v\u00f5ib sisaldada ainult \u00fchte plussm\u00e4rki. Seet\u00f5ttu saame m\u00f5lemal kahendv\u00e4ljenduse puul l\u00e4bi viia esimese s\u00fcgavuse otsingu algoritmi (DFS) ja iga muutuja \u00fcles lugeda. Kaks avaldisepuud on v\u00f5rdsed, kui m\u00f5lemad puud sisaldavad sama arvu muutujaid.<\/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
DFS<\/a> t\u00f6\u00f6tab O (N) ajas, kus N on m\u00f5lema binaaravaldise puu s\u00f5lmede arv. Ruumi keerukus on O(N), kuna me kasutame virna rekursiooni kaudu ja samuti peame registreerima iga muutuja loendurid.<\/p>\n
V\u00f5rdlemaks, kas kaks r\u00e4sikaarti on v\u00f5rdsed (unordered_map<\/a> ), saame neid lihtsalt v\u00f5rrelda C++ keeles, kasutades topeltv\u00f5rdusm\u00e4rki.<\/p>\n
:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Esimese s\u00fcgavuse otsingu algoritm, et kontrollida, kas kaks v\u00e4ljendipuud on samav\u00e4\u00e4rsed<\/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":[718,749,833,894,842],"tags":[1165],"class_list":["post-233204","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-arendaja","category-avatud-laehtekoodiga","category-juhend-algajatele","category-kood","category-opetused","tag-affiai-et"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts\/233204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/comments?post=233204"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts\/233204\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/media?parent=233204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/categories?post=233204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/tags?post=233204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}