ধরুন আমাদের একটি বাইনারি ট্রি আছে এবং কাজটি হল এটি নিজের একটি প্রতিসাম্য তৈরি করে কিনা তা পরীক্ষা করা। একটি সিমেট্রিক বাইনারি গাছ নিজের আয়নার প্রতিচ্ছবি তৈরি করে।
উদাহরণস্বরূপ
ইনপুট-1:
আউটপুট:
True
ব্যাখ্যা:
যেহেতু প্রদত্ত বাইনারি গাছটি নিজের আয়নার প্রতিচ্ছবি তৈরি করে, তাই আউটপুটটি সত্য।
ইনপুট-2:
আউটপুট:
False
ব্যাখ্যা:
যেহেতু প্রদত্ত বাইনারি গাছটি নিজের একটি মিরর ইমেজ তৈরি করে না, তাই এটি প্রতিসম নয়৷
এই সমস্যা সমাধানের পদ্ধতি
একটি সিমেট্রিক বাইনারি ট্রি হল এমন একটি গাছ যা নিজেই নিজের মিরর ইমেজ, যার মানে গাছের বাম এবং ডান নোডগুলি একই কিনা তা আমাদের পরীক্ষা করতে হবে৷
একটি বুলিয়ান ফাংশন প্রাথমিকভাবে বাম নোড এবং ডান নোডের জন্য পরীক্ষা করবে। যদি নোডগুলি খালি বা NULL হয়, তাহলে এটি True ফিরে আসবে। অন্যান্য ক্ষেত্রে, আমরা এটির বাম বা ডান সন্তান আছে কিনা তা পরীক্ষা করব, তারপর এটি অবশ্যই একই হতে হবে যাতে এটি একটি প্রতিসম গাছ হয়৷
- একটি বাইনারি ট্রি নিন যাতে মূল এবং এর বাচ্চা থাকে।
- একটি বুলিয়ান হেল্পার ফাংশন হেল্পার (নোড*রুট1, নোড*রুট2) একই গাছের দুটি শিকড় নেয় যা বাম শিশু এবং ডান শিশু একই কিনা তা পরীক্ষা করতে সাহায্য করে।
- যদি গাছটি খালি বা NULL হয়, তাহলে আমরা সত্যে ফিরে আসব।
- বৃক্ষের বাম নোড এবং ডান নোড সমান কিনা বারবার পরীক্ষা করুন৷
- উপরের সমস্ত শর্ত সন্তোষজনক না হলে মিথ্যা ফেরত দিন।
উদাহরণ
#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
ব্যাখ্যা:
যেহেতু প্রদত্ত গাছটি প্রতিসম নয়, তাই আমরা ফলস হিসাবে আউটপুট পাই।
