C++-এ বাইনারি সার্চ ট্রি থেকে টার্গেটের নিকটতম K এলিমেন্ট বের করা

সমস্যা

একটি BST এবং ফ্লোটিং-পয়েন্ট টার্গেট মান দেওয়া। BST-এ থেকে টার্গেটের নিকটতম kটি মান বের করুন।

অ্যালগরিদম: দুটি স্ট্যাক (ইনঅর্ডার + রিভার্স ইনঅর্ডার)

1. pushSmaller(node, stack, target): টার্গেট থেকে ছোট মানগুলো স্ট্যাকে পুশ করুন (ইনঅর্ডার ট্রাভার্সাল)।
2. pushLarger(node, stack, target): টার্গেট থেকে বড়/সমান মানগুলো স্ট্যাকে পুশ করুন (রিভার্স ইনঅর্ডার)।
3. k বার:
   • দুই স্ট্যাকের টপ তুলনা করুন, টার্গেটের নিকটতম যেটি সেটি পপ করে রেজাল্টে যোগ করুন।
   • পপ করা নোডের চাইল্ডকে উপযুক্ত স্ট্যাকে পুশ করুন (নেক্সট প্রিডিসেসর/সাক্সেসর পেতে)।

C++ কোড (সংক্ষিপ্ত)

class Solution {
    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;
        }
    }
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> ret;
        stack<TreeNode*> smaller, 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;
    }
};

উদাহরণ আউটপুট

Input: BST=[4,2,5,1,3], target=3.7142, k=2
Output: [4, 3]