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