मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) और एक लक्ष्य मान है; हमें उस दिए गए BST में k मान खोजने हैं जो लक्ष्य के सबसे निकट हैं। यहां लक्ष्य मान एक फ्लोटिंग-पॉइंट संख्या है। हम मान सकते हैं कि k हमेशा वैध है, और k ≤ कुल नोड्स।
उदाहरण के लिए, यदि इनपुट इस तरह का है:

लक्ष्य = 3.714286, और k = 2, तो आउटपुट [4,3] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- pushSmaller() फंक्शन परिभाषित करें, जो नोड, स्टैक st, और लक्ष्य लेता है:
- जब तक नोड मौजूद है:
- यदि नोड का मान < लक्ष्य, तो नोड को st में डालें, नोड := नोड का दायां
- अन्यथा नोड := नोड का बायां
- जब तक नोड मौजूद है:
- pushLarger() फंक्शन परिभाषित करें, जो नोड, स्टैक st, लक्ष्य लेता है:
- जब तक नोड मौजूद है:
- यदि नोड का मान >= लक्ष्य, तो नोड को st में डालें, नोड := नोड का बायां
- अन्यथा नोड := नोड का दायां
- जब तक नोड मौजूद है:
- मेन मेथड से:
- रिट नामक एक ऐरे परिभाषित करें
- स्मॉलर नामक एक स्टैक परिभाषित करें
- लार्जर नामक एक स्टैक परिभाषित करें
- pushLarger(रूट, लार्जर, लक्ष्य)
- pushSmaller(रूट, स्मॉलर, लक्ष्य)
- जब तक k शून्येतर है, प्रत्येक चरण में k घटाएं:
- यदि स्मॉलर खाली नहीं है और (लार्जर खाली है या |लक्ष्य - स्मॉलर के शीर्ष तत्व का मान| < |लक्ष्य - लार्जर के शीर्ष तत्व|):
- करंट = स्मॉलर का शीर्ष तत्व
- स्मॉलर से तत्व हटाएं
- करंट के मान को रिट के अंत में डालें
- pushSmaller(करंट का बायां, स्मॉलर, लक्ष्य)
- अन्यथा:
- करंट = लार्जर का शीर्ष तत्व
- लार्जर से तत्व हटाएं
- करंट के मान को रिट के अंत में डालें
- pushLarger(करंट का दायां, लार्जर, लक्ष्य)
- यदि स्मॉलर खाली नहीं है और (लार्जर खाली है या |लक्ष्य - स्मॉलर के शीर्ष तत्व का मान| < |लक्ष्य - लार्जर के शीर्ष तत्व|):
- रिट लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ 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: vector<int> closestKValues(TreeNode* root, double target, int k){ vector<int> ret; stack<TreeNode*> smaller; stack<TreeNode*> larger; pushLarger(root, larger, target); pushSmaller(root, smaller, target); while (k--) { if (!smaller.empty() && (larger.empty() || (abs(target - smaller.top()->val) < abs(target - larger.top()->val)))) { TreeNode* curr = smaller.top(); smaller.pop(); ret.push_back(curr->val); pushSmaller(curr->left, smaller, target); } else { TreeNode* curr = larger.top(); larger.pop(); ret.push_back(curr->val); pushLarger(curr->right, larger, target); } } return ret; } void pushSmaller(TreeNode* node, stack <TreeNode*>& st, double target){ while (node) { if (node->val < target) { st.push(node); node = node->right; } else { node = node->left; } } } void pushLarger(TreeNode* node, stack <TreeNode*>& st, double target){ while (node) { if (node->val >= target) { st.push(node); node = node->left; } else node = node->right; } } }; main(){ Solution ob; vector<int> v = {4,2,5,1,3}; TreeNode *root = make_tree(v); print_vector(ob.closestKValues(root, 3.7142, 2)); } इनपुट
{4,2,5,1,3}, 3.7142, 2 आउटपुट
[4, 3, ]