{"id":233177,"date":"2023-02-07T14:50:00","date_gmt":"2023-02-07T11:50:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233177"},"modified":"2023-02-07T14:53:15","modified_gmt":"2023-02-07T11:53:15","slug":"depth-first-search-algoritm-foer-att-kontrollera-om-tvaa-uttryckstraed-aer-likvaerdiga","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/sv\/depth-first-search-algoritm-foer-att-kontrollera-om-tvaa-uttryckstraed-aer-likvaerdiga\/","title":{"rendered":"Depth First Search Algoritm f\u00f6r att kontrollera om tv\u00e5 uttryckstr\u00e4d \u00e4r likv\u00e4rdiga"},"content":{"rendered":"\n
\n

Ett bin\u00e4rt uttryckstr\u00e4d \u00e4r ett slags bin\u00e4rt tr\u00e4d som anv\u00e4nds f\u00f6r att representera aritmetiska uttryck. Varje nod i ett bin\u00e4rt uttryckstr\u00e4d har antingen noll eller tv\u00e5 barn. L\u00f6vnoder (noder med 0 barn) motsvarar operander (variabler), och interna noder (noder med tv\u00e5 barn) motsvarar operatorerna. I detta problem tar vi bara h\u00e4nsyn till ’+’-operatorn (dvs addition).<\/p>\n

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

uttryck-bin\u00e4rt-tr\u00e4d<\/p>\n

Du f\u00e5r r\u00f6tterna till tv\u00e5 bin\u00e4ra uttryckstr\u00e4d, root1 och root2. Returnera sant om de tv\u00e5 bin\u00e4ra uttryckstr\u00e4den \u00e4r ekvivalenta. Annars, returnera falskt.<\/p>\n

Tv\u00e5 bin\u00e4ra uttryckstr\u00e4d \u00e4r likv\u00e4rdiga om de utv\u00e4rderas till samma v\u00e4rde oavsett vad variablerna \u00e4r inst\u00e4llda p\u00e5.<\/p>\n

Uppf\u00f6ljning: Vad kommer du att \u00e4ndra i din l\u00f6sning om tr\u00e4det ocks\u00e5 st\u00f6der ’-’-operatorn (dvs subtraktion)?<\/p>\n

Exempel 1:
\nIndata: rot1 = [x], rot2 = [x]
\nUtdata: sant<\/p>\n

Exempel 2:
\nIndata: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
\nUtdata: sant
\nF\u00f6rklaring: a + (b + c) == (b + c) + a<\/p>\n

Exempel 3:
\nIndata: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
\nOutput: false
\nF\u00f6rklaring: a + (b + c) != (b + d) + a<\/p>\n

Begr\u00e4nsningar:
\nAntalet noder i b\u00e5da tr\u00e4den \u00e4r lika, udda och i intervallet [1, 4999].
\nNode.val \u00e4r ’+’ eller en liten engelsk bokstav.
\nDet \u00e4r garanterat att det angivna tr\u00e4det \u00e4r ett giltigt bin\u00e4rt uttryckstr\u00e4d.<\/p>\n

Tips:
\nR\u00e4kna f\u00f6r varje variabel hur m\u00e5nga g\u00e5nger den f\u00f6rekom i det f\u00f6rsta tr\u00e4det.
\nG\u00f6r samma sak f\u00f6r det andra tr\u00e4det och kontrollera om antalet \u00e4r detsamma f\u00f6r b\u00e5da tr\u00e4den.<\/p>\n<\/blockquote>\n

Depth First Search Algoritm med Hash-tabell<\/h3>\n

Eftersom uttryckstr\u00e4det<\/a> \u00e4r bin\u00e4rt och bara kan inneh\u00e5lla en plussymbol. D\u00e4rf\u00f6r kan vi utf\u00f6ra Depth First Search Algorithm (DFS) p\u00e5 b\u00e5da bin\u00e4ra uttryckstr\u00e4den och r\u00e4kna varje variabel. De tv\u00e5 uttryckstr\u00e4den \u00e4r lika om b\u00e5da tr\u00e4den inneh\u00e5ller samma antal variabler.<\/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 k\u00f6rs i O(N) -tid<\/a> d\u00e4r N \u00e4r antalet noder i b\u00e5da bin\u00e4ra uttryckstr\u00e4den. Utrymmeskomplexiteten \u00e4r O(N) eftersom vi anv\u00e4nder stack via rekursion och \u00e4ven beh\u00f6ver registrera r\u00e4knarna f\u00f6r varje variabel.<\/p>\n
F\u00f6r att j\u00e4mf\u00f6ra om tv\u00e5 hash-kartor \u00e4r lika (unordered_map<\/a> ), kan vi helt enkelt j\u00e4mf\u00f6ra dem i C++ med det dubbla likhetstecknet.<\/p>\n
Inspelningsk\u00e4lla:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Depth First Search Algoritm f\u00f6r att kontrollera om tv\u00e5 uttryckstr\u00e4d \u00e4r likv\u00e4rdiga<\/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":[838,848,901,755,724],"tags":[1173],"class_list":["post-233177","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-guide-foer-nyboerjare","category-handledningar","category-koda","category-oeppen-kaella","category-utvecklaren","tag-affiai-sv"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/233177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/comments?post=233177"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/233177\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media\/224845"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media?parent=233177"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/categories?post=233177"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/tags?post=233177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}