मान लीजिए कि हमारे पास एक बाइनरी ट्री है और कार्य यह जांचना है कि यह स्वयं की समरूपता का निर्माण करता है या नहीं। एक सममित बाइनरी ट्री स्वयं की दर्पण छवि का निर्माण करता है।
उदाहरण के लिए
इनपुट-1:
<मजबूत> 
आउटपुट:
True
स्पष्टीकरण:
चूंकि दिया गया बाइनरी ट्री स्वयं की मिरर इमेज बनाता है, आउटपुट ट्रू होता है।
इनपुट-2:
<मजबूत> 
आउटपुट:
False
स्पष्टीकरण:
चूँकि दिया गया बाइनरी ट्री स्वयं का दर्पण प्रतिबिम्ब नहीं बनाता है, यह सममित नहीं है।
इस समस्या को हल करने का तरीका
एक सममित बाइनरी ट्री एक पेड़ है जो स्वयं की दर्पण छवि है, जिसका अर्थ है कि हमें यह जांचना होगा कि पेड़ के बाएं और दाएं नोड समान हैं या नहीं।
एक बूलियन फ़ंक्शन प्रारंभ में बाएं नोड और दाएं नोड की जांच करेगा। यदि नोड्स खाली या NULL हैं, तो यह ट्रू वापस आ जाएगा। अन्य मामलों के लिए, हम जाँच करेंगे कि क्या इसमें बाएँ या दाएँ बच्चे हैं, तो यह समान होना चाहिए ताकि यह एक सममित वृक्ष हो।
- एक बाइनरी ट्री लें जिसमें जड़ और उसके बच्चे हों।
- एक बूलियन हेल्पर फंक्शन हेल्पर(नोड*रूट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
स्पष्टीकरण:
चूंकि दिया गया पेड़ सममित नहीं है, इसलिए हमें आउटपुट असत्य के रूप में मिलता है।