{"id":233193,"date":"2023-02-07T14:50:00","date_gmt":"2023-02-07T11:50:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233193"},"modified":"2023-02-07T14:53:15","modified_gmt":"2023-02-07T11:53:15","slug":"syvyys-ensin-hakualgoritmi-tarkistaaksesi-ovatko-kaksi-lausekepuuta-samanarvoisia","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/fi\/syvyys-ensin-hakualgoritmi-tarkistaaksesi-ovatko-kaksi-lausekepuuta-samanarvoisia\/","title":{"rendered":"Syvyys ensin -hakualgoritmi tarkistaaksesi, ovatko kaksi lausekepuuta samanarvoisia"},"content":{"rendered":"\n
\n

Bin\u00e4\u00e4rilausekepuu on er\u00e4\u00e4nlainen bin\u00e4\u00e4ripuu, jota k\u00e4ytet\u00e4\u00e4n edustamaan aritmeettisia lausekkeita. Jokaisella binaarilausekepuun solmulla on joko nolla tai kaksi alapistett\u00e4. Lehtisolmut (solmut, joissa on 0 lasta) vastaavat operandeja (muuttujia) ja sis\u00e4iset solmut (solmut, joissa on kaksi lasta) vastaavat operaattoreita. T\u00e4ss\u00e4 teht\u00e4v\u00e4ss\u00e4 huomioidaan vain ’+’-operaattori (eli summaus).<\/p>\n

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

lauseke-bin\u00e4\u00e4ri-puu<\/p>\n

Sinulle annetaan kahden binaarilausekepuun juuret, juuri1 ja juuri2. Palauttaa tosi, jos kaksi binaarilausekepuuta ovat samanarvoisia. Muussa tapauksessa palauta false.<\/p>\n

Kaksi binaarilausekepuuta ovat ekvivalentteja, jos ne evaluoivat samaan arvoon riippumatta siit\u00e4, mihin muuttujat on asetettu.<\/p>\n

Seuranta: Mit\u00e4 muutat ratkaisussasi, jos puu tukee my\u00f6s ’-’-operaattoria (eli v\u00e4hennyslaskua)?<\/p>\n

Esimerkki 1:
\nTulo: root1 = [x], root2 = [x]
\nTulos: tosi<\/p>\n

Esimerkki 2:
\nSy\u00f6tt\u00f6: root1 = [+,a,+,nolla,null,b,c], root2 = [+,+,b,c,a]
\nTulos: true
\nSelitys: a + (b + c) == (b + c) + a<\/p>\n

Esimerkki 3:
\nSy\u00f6tt\u00f6: root1 = [+,a,+,nolla,null,b,c], root2 = [+,+,b,d,a]
\nTulos: ep\u00e4tosi
\nSelitys: a + (b + c) != (b + d) + a<\/p>\n

Rajoitukset:
\nSolmujen lukum\u00e4\u00e4r\u00e4 molemmissa puissa on yht\u00e4 suuri, pariton ja alueella [1, 4999].
\nNode.val on ’+’ tai pieni englanninkielinen kirjain.
\nOn taattu, ett\u00e4 annettu puu on kelvollinen bin\u00e4\u00e4rilausekepuu.<\/p>\n

Vihjeit\u00e4:
\nLaske kunkin muuttujan kohdalla, kuinka monta kertaa se esiintyi ensimm\u00e4isess\u00e4 puussa.
\nTee sama toiselle puulle ja tarkista, onko molemmissa puussa sama luku.<\/p>\n<\/blockquote>\n

Syvyys ensin -hakualgoritmi hash-taulukolla<\/h3>\n

Koska lausekepuu<\/a> on binaarinen ja voi sis\u00e4lt\u00e4\u00e4 vain yhden plussymbolin. Siksi voimme suorittaa Depth First Search Algorithmin (DFS) molemmille bin\u00e4\u00e4rilausekepuille ja laskea kunkin muuttujan. N\u00e4m\u00e4 kaksi lausekepuuta ovat yht\u00e4 suuret, jos molemmat puut sis\u00e4lt\u00e4v\u00e4t saman m\u00e4\u00e4r\u00e4n muuttujia.<\/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> suoritetaan O(N) -ajassa, miss\u00e4 N on solmujen lukum\u00e4\u00e4r\u00e4 molemmissa bin\u00e4\u00e4rilausekepuissa. Tilan monimutkaisuus on O(N), koska k\u00e4yt\u00e4mme pinoa rekursion kautta ja meid\u00e4n on my\u00f6s tallennettava jokaisen muuttujan laskurit.<\/p>\n
Vertaaksemme, ovatko kaksi hash-karttaa yht\u00e4 suuret (unordered_map<\/a> ), voimme yksinkertaisesti verrata niit\u00e4 C++:ssa k\u00e4ytt\u00e4m\u00e4ll\u00e4 kaksoisyht\u00e4ysmerkki\u00e4.<\/p>\n
:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Syvyys ensin -hakualgoritmi tarkistaaksesi, ovatko kaksi lausekepuuta samanarvoisia<\/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":[750,719,895,834,843],"tags":[1166],"class_list":["post-233193","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-avoin-laehdekoodi","category-kehittaejae","category-koodi","category-opas-aloittelijoille","category-opetusohjelmia","tag-affiai-fi"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts\/233193","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/comments?post=233193"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts\/233193\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/media?parent=233193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/categories?post=233193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/tags?post=233193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}