मान लीजिए हमारे पास एक बाइनरी ट्री, एक लक्ष्य नोड, और एक मान K है। हमें उन सभी नोड्स के मानों की सूची ढूंढनी है जिनकी दूरी लक्ष्य नोड से K है।
उदाहरण के लिए, यदि इनपुट root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 है, तो आउटपुट [7,4,1] होगा, क्योंकि लक्ष्य नोड से दूरी 2 पर नोड्स के मान 7, 4, और 1 हैं।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
dfs()फ़ंक्शन परिभाषित करें जो प्रत्येक नोड के माता-पिता को मैप में संग्रहीत करता है।- मुख्य विधि में:
- उत्तर सरणी ans परिभाषित करें।
- dfs(root) कॉल करके माता-पिता मैप भरें।
- (नोड, स्तर) युग्म के लिए एक कतार q परिभाषित करें।
- {target, 0} को q में डालें।
- देखे गए नोड्स के लिए एक सेट visited परिभाषित करें, target डालें।
- जब तक q खाली न हो:
- सामने का तत्व निकालें।
- यदि स्तर == K, तो नोड का मान ans में जोड़ें।
- बाएं, दाएं, और माता-पिता नोड्स को यदि वैध और अनदेखे हैं, तो स्तर+1 के साथ q में डालें।
- ans लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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, ]