मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक लक्ष्य मान है; हमें उस BST में k मान ढूंढने हैं जो लक्ष्य के सबसे करीब हैं। हमें ध्यान रखना होगा कि लक्ष्य मान एक फ्लोटिंग-पॉइंट संख्या है। हम मान सकते हैं कि k हमेशा वैध है, और k ≤ कुल नोड्स।
तो, यदि इनपुट इस तरह है
target = 3.714286, और k = 2, तो आउटपुट [4,3] होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
pushSmaller() नामक एक फ़ंक्शन परिभाषित करें, जो node, stack st, और target लेगा,
जब तक node मौजूद नहीं है, करें −
यदि node का val < target, तो −
node को st में डालें
node := node का right
अन्यथा
node := node का left
pushLarger() नामक एक फ़ंक्शन परिभाषित करें, जो node, stack st, target लेगा,
जब तक node खाली नहीं है, करें −
यदि node का val >= target, तो −
node को st में डालें
node := node का left
अन्यथा
node := node का right
मुख्य विधि से निम्नलिखित करें −
एक ऐरे ret परिभाषित करें
एक स्टैक smaller परिभाषित करें
एक स्टैक larger परिभाषित करें
pushLarger(root, larger, target)
pushSmaller(root, smaller, target)
जब तक k शून्येतर है, प्रत्येक चरण में k घटाएं, करें −
यदि smaller खाली नहीं है और (larger खाली है या |target - smaller के शीर्ष तत्व का मान| < |target - larger के शीर्ष तत्व|)
curr = smaller का शीर्ष तत्व
smaller से तत्व हटाएं
curr के val को ret के अंत में डालें
pushSmaller(curr का left, smaller, target)
अन्यथा
curr = larger का शीर्ष तत्व
larger से तत्व हटाएं
curr के val को ret के अंत में डालें
pushSmaller(curr का right, larger, target)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> 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: 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, ]
