मान लीजिए कि हमारे पास एक बाइनरी ट्री, एक लक्ष्य नोड और एक मान K है। हमें उन सभी नोड्स के मानों की एक सूची ढूंढनी है, जिनकी लक्ष्य नोड से दूरी K है।
इसलिए, यदि इनपुट रूट =[3,5,1,6,2,0,8, नल, नल, 7,4], लक्ष्य =5, के =2 जैसा है, तो आउटपुट [7,4 होगा ,1], ऐसा इसलिए है क्योंकि लक्ष्य नोड से दूरी 2 वाले नोड्स के मान 7, 4 और 1 हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन dfs() को परिभाषित करें, यह नोड लेगा, इसे NULL के साथ प्रारंभ करें,
-
यदि नोड शून्य है, तो -
-
वापसी
-
-
माता-पिता [नोड] :=पा
-
dfs (नोड के बाएं, नोड)
-
dfs (नोड का दायां, नोड)
-
मुख्य विधि से निम्न कार्य करें -
-
एक सरणी को परिभाषित करें ans
-
dfs(रूट)
-
(नोड, मान) जोड़ी के लिए एक कतार q परिभाषित करें
-
q में { लक्ष्य, 0 } डालें
-
देखे गए नाम के एक सेट को परिभाषित करें
-
विज़िट किए गए लक्ष्य में डालें
-
जबकि (नहीं q खाली है), करें -
-
एक जोड़ी p परिभाषित करें:=q का पहला तत्व
-
q से तत्व हटाएं
-
स्तर :=अस्थायी का दूसरा तत्व
-
नोड =अस्थायी का पहला तत्व।
-
यदि स्तर k के समान है, तो -
-
उत्तर के अंत में नोड का मान डालें
-
-
यदि नोड का बायां भाग शून्य नहीं है और स्तर + 1 <=k और बाएं नोड का दौरा नहीं किया जाता है, तो
-
{नोड के बाएं, स्तर + 1}) को q
. में डालें -
नोड के बाईं ओर देखे गए सेट में डालें
-
-
यदि नोड का दायां शून्य नहीं है और स्तर + 1 <=k और नोड का दायां नहीं देखा जाता है, तो
-
q में {नोड का दायां, स्तर + 1}) डालें
-
नोड के दाईं ओर विज़िट किए गए सेट में डालें
-
-
यदि माता-पिता [नोड] NULL नहीं है और स्तर + 1 <=k और माता-पिता [नोड] का दौरा नहीं किया गया है, तो -
-
q में { पैरेंट [नोड], लेवल + 1 } डालें
-
माता-पिता [नोड] को विज़िट में डालें
-
-
-
वापसी उत्तर
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
map <TreeNode*, TreeNode*> parent;
void dfs(TreeNode* node, TreeNode* pa = NULL){
if (!node)
return;
parent[node] = pa;
dfs(node->left, node);
dfs(node->right, node);
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> ans;
parent.clear();
dfs(root);
queue<pair<TreeNode*, int> > q;
q.push({ target, 0 });
set<TreeNode*> visited;
visited.insert(target);
while (!q.empty()) {
pair<TreeNode*, int> temp = q.front();
q.pop();
int level = temp.second;
TreeNode* node = temp.first;
if (level == k) {
ans.push_back(node->val);
}
if ((node->left && node->left->val != 0) && level + 1 <= k && !visited.count(node->left)) {
q.push({ node->left, level + 1 });
visited.insert(node->left);
}
if ((node->right && node->right->val != 0) && level + 1 <= k && !visited.count(node->right)){
q.push({ node->right, level + 1 });
visited.insert(node->right);
}
if (parent[node] != NULL && level + 1 <= k && !visited.count(parent[node])) {
q.push({ parent[node], level + 1 });
visited.insert(parent[node]);
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
TreeNode *root = make_tree(v);
TreeNode *target = root->left;
print_vector(ob.distanceK(root, target, 2));
} इनपुट
{3,5,1,6,2,0,8,NULL,NULL,7,4} आउटपुट
[7, 4, 1, ]
