इस समस्या में, हमें एक बाइनरी ट्री, एक लक्ष्य नोड और एक पूर्णांक K दिया जाता है। हमें ट्री के सभी नोड्स को प्रिंट करना होता है जो लक्ष्य नोड से K की दूरी पर होते हैं। ।
बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो नोड (एक/दो/कोई नहीं) होते हैं।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
के =2
लक्ष्य नोड:9
आउटपुट -
5 1 3.
स्पष्टीकरण -
दूरी को नोड के लिए उच्च, निम्न या समान स्तर पर लिया जा सकता है। इसलिए, हम तदनुसार नोड्स लौटाएंगे।
इस समस्या को हल करने के लिए हमें यह समझना होगा कि किस प्रकार के नोड हैं जो लक्ष्य नोड से K दूरी पर हैं।
उपरोक्त परीक्षा से, हम देख सकते हैं कि k दूर के नोड्स लक्ष्य नोड के सबट्री (5 और 1) में हो सकते हैं या लक्ष्य नोड (3) के पूर्वज के सबट्री में कहीं भी हो सकते हैं।
अब, पहले मामले का समाधान खोजने की विधि लक्ष्य नोड के उपप्रकार को पार करके है, और जांचें कि क्या लक्ष्य से नोड की दूरी K है। यदि हाँ, तो नोड को प्रिंट करें।
दूसरे मामले के लिए, हमें लक्ष्य के लिए पूर्वज नोड्स और इन पूर्वजों के उपप्रकार की जांच करनी होगी और सभी को K से दूरी पर प्रिंट करना होगा।
नीचे दिया गया कार्यक्रम हमारे समाधान के कार्यान्वयन को दिखाएगा -
उदाहरण
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
void printSubtreeNodes(node *root, int k) {
if (root == NULL || k < 0) return;
if (k==0){
cout<<root->data<<"\t";
return;
}
printSubtreeNodes(root->left, k-1);
printSubtreeNodes(root->right, k-1);
}
int printKNodes(node* root, node* target , int k){
if (root == NULL) return -1;
if (root == target){
printSubtreeNodes(root, k);
return 0;
}
int dl = printKNodes(root->left, target, k);
if (dl != -1){
if (dl + 1 == k)
cout<<root->data<<"\t";
else
printSubtreeNodes(root->right, k-dl-2);
return 1 + dl;
}
int dr = printKNodes(root->right, target, k);
if (dr != -1){
if (dr + 1 == k)
cout << root->data << endl;
else
printSubtreeNodes(root->left, k-dr-2);
return 1 + dr;
}
return -1;
}
node *insertNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main(){
node * root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->right = insertNode(4);
root->right->left = insertNode(8);
root->right->right = insertNode(10);
root->right->right->left = insertNode(5);
root->right->right->right = insertNode(1);
node * target = root->right;
int K = 2;
cout<<"Nodes at distance "<<K<<" from the target node are :\n";
printKNodes(root, target, K);
return 0;
} आउटपुट
Nodes at distance 2 from the target n tode are − 5 1 3