ต้นไม้สมมาตรใน C++

สมมุติว่าเรามีไบนารีทรีและงานคือตรวจสอบว่าสร้างสมมาตรของตัวมันเองหรือไม่ ต้นไม้ไบนารีสมมาตรสร้างภาพสะท้อนของตัวเอง

ตัวอย่าง

อินพุต-1:

ผลลัพธ์:

True

คำอธิบาย:

เนื่องจากไบนารีทรีที่กำหนดจะสร้างภาพสะท้อนของตัวมันเอง ผลลัพธ์ที่ได้จึงเป็น True

อินพุต-2:

ผลลัพธ์:

False

คำอธิบาย:

เนื่องจากไบนารีทรีที่ให้มาไม่ได้สร้างภาพสะท้อนของตัวเอง จึงไม่สมมาตร

แนวทางในการแก้ปัญหานี้

ต้นไม้ไบนารีสมมาตรคือต้นไม้ที่เป็นภาพสะท้อนของมันเอง ซึ่งหมายความว่าเราต้องตรวจสอบว่าโหนดซ้ายและขวาของต้นไม้เหมือนกันหรือไม่

ฟังก์ชันบูลีนจะตรวจสอบโหนดด้านซ้ายและโหนดด้านขวาในขั้นต้น หากโหนดว่างเปล่าหรือเป็น NULL โหนดจะคืนค่าเป็น True สำหรับกรณีอื่นๆ เราจะตรวจสอบว่ามีรายการย่อยด้านซ้ายหรือด้านขวา จากนั้นจะต้องเหมือนกันเพื่อให้เป็นต้นไม้สมมาตร

• นำ Binary Tree ที่มีรากและลูกของมัน
• ตัวช่วยฟังก์ชันตัวช่วยบูลีน (node*root1, node*root2) รับสองรูตของทรีเดียวกัน ซึ่งช่วยตรวจสอบว่าลูกด้านซ้ายและชายด์ด้านขวาเหมือนกันหรือไม่
• ถ้าต้นไม้ว่างเปล่าหรือ NULL เราจะคืนค่า True
• ตรวจสอบซ้ำๆ ว่าโหนดด้านซ้ายและโหนดด้านขวาของแผนภูมิมีค่าเท่ากันหรือไม่
• คืนค่าเป็นเท็จหากเงื่อนไขข้างต้นไม่เป็นไปตามเงื่อนไขทั้งหมด

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
bool helper(struct treenode * root1, struct treenode * root2) {
   if (root1 == NULL and root2 == NULL)
      return true;
   if (root1 and root2 and root1 -> data == root2 -> data)
      return (helper(root1 -> left, root2 -> right) and helper(root1 -> right, root2 -> left));
   return false;
}
bool isSymmetry(struct treenode * root) {
   return helper(root, root);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   if (isSymmetry(root)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

ผลลัพธ์

False

คำอธิบาย:

เนื่องจากต้นไม้ที่ระบุไม่สมมาตร เราจึงได้ผลลัพธ์เป็นเท็จ