พลิกต้นไม้ไบนารีที่เทียบเท่าใน C ++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องพลิกต้นไม้ไบนารี พลิกระบุ:เลือกโหนดใด ๆ และสลับทรีย่อยย่อยซ้ายและขวา ตอนนี้ไบนารีทรี X เท่ากับฟลิปเทียบเท่ากับไบนารีทรี Y ถ้าหากว่าเราสามารถสร้าง Y จาก X ได้หลังจากการดำเนินการพลิกจำนวนหนึ่ง เราต้องเขียนวิธีการที่กำหนดว่าต้นไม้ไบนารีสองต้นมีค่าเท่ากันหรือไม่ ต้นไม้ถูกกำหนดโดยโหนดรูท root1 และ root2 ดังนั้นหากต้นไม้เป็น −

ผลลัพธ์ที่ได้จะเป็นจริง หากเราพลิกโหนดด้วยค่า 1, 3 และ 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชันแบบเรียกซ้ำหนึ่งฟังก์ชัน Solve() ซึ่งจะใช้ต้นไม้สองต้น t1 และ t2

• ถ้า root1 และ root2 เป็นโมฆะ ให้คืนค่า true

• มิฉะนั้น เมื่อ root1 เป็นโมฆะ หรือ root2 เป็นโมฆะ ให้คืนค่าเท็จ

• มิฉะนั้น เมื่อ (t1 และ t2 ทั้งคู่ไม่มีทรีย่อยซ้าย) หรือ (t1 และ t2 ทั้งคู่มีทรีย่อยซ้าย และค่าของทรีย่อยด้านซ้ายของทั้งสองโหนดจะเท่ากัน) ดังนั้น

  • คืนค่าการแก้ (ด้านซ้ายของ root1 ด้านซ้ายของ root2) และการแก้ปัญหา (ด้านขวาของ root1 ด้านขวาของ root2)

• อย่างอื่น

  • คืนค่าการแก้ (ด้านซ้ายของ root1 ด้านขวาของ root2) และการแก้ปัญหา (ด้านขวาของ root1 ด้านซ้ายของ root2)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;คลาส TreeNode{ สาธารณะ:int val; TreeNode *ซ้าย *ขวา; TreeNode (ข้อมูล int) { val =data; ซ้าย =NULL; ขวา =NULL; }};การแทรกเป็นโมฆะ (TreeNode **root, int val){ คิว q; q.push(*root); ในขณะที่ (q.size()){ TreeNode *temp =q.front(); q.ป๊อป(); if(!temp->left){ if(val !=NULL) temp->left =new TreeNode(val); อื่น temp->left =ใหม่ TreeNode(0); กลับ; }อื่น{ q.push(ชั่วคราว->ซ้าย); } if(!temp->right){ if(val !=NULL) temp->right =new TreeNode(val); อื่น temp->right =ใหม่ TreeNode(0); กลับ; }อื่น{ q.push(ชั่วคราว->ขวา); } }}TreeNode *make_tree(vector v){ TreeNode *root =TreeNode ใหม่(v[0]); สำหรับ(int i =1; ival !=root2->val) คืนค่าเท็จ อื่น if((!root1->left &&!root2->left) || (root1->left &&root2->left &&root1->left->val ==root2->left->val)){ return flipEquiv (root1->left, root2->left) &&flipEquiv(root1->right, root2->right); }อื่น{ return flipEquiv(root1->left, root2->right) &&flipEquiv(root1->right, root2->left); } }};main(){ vector v ={1,2,3,4,5,6,NULL,NULL,NULL,7,8}; TreeNode *r1 =make_tree(v); เวกเตอร์ v1 ={1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7}; TreeNode *r2 =make_tree(v); โซลูชัน ob; ศาล <<(ob.flipEquiv(r1, r2));}

อินพุต

ผลลัพธ์

1