C++-এ বাইনারি সার্চ ট্রি থেকে টার্গেটের নিকটতম K মান (Closest Binary Search Tree Value II)

ধরি আমাদের একটি বাইনারি সার্চ ট্রি (BST) এবং একটি টার্গেট ভ্যালু আছে। আমাদের সেই BST-এ থেকে k টি মান বের করতে হবে যেগুলো টার্গেটের সবচেয়ে निकট। টার্গেট ভ্যালু একটি ফ্লোটিং পয়েন্ট নম্বর। k সবসময় বৈধ এবং k <= মোট নোড।

উদাহরণস্বরূপ, ট্রি:

target = 3.714286, k = 2 হলে আউটপুট হবে [4, 3]।

সমাধানের ধাপসমূহ

• pushSmaller(node, st, target) ফাংশন:
  • যখন node নন-নাল:
    • যদি node->val < target: st.push(node); node = node->right
    • অন্যথায়: node = node->left
• pushLarger(node, st, target) ফাংশন:
  • যখন node নন-নাল:
    • যদি node->val >= target: st.push(node); node = node->left
    • অন্যথায়: node = node->right
• মেইন মেথড:
  • ret অ্যারে, দুটি স্ট্যাক smaller এবং larger
  • pushLarger(root, larger, target)
  • pushSmaller(root, smaller, target)
  • যখন k > 0:
    • যদি smaller খালি না এবং (larger খালি বা |target - smaller.top()->val| < |target - larger.top()->val|):
      • curr = smaller.top(); smaller.pop()
      • ret.push_back(curr->val)
      • pushSmaller(curr->left, smaller, target)
    • অন্যথায়:
      • curr = larger.top(); larger.pop()
      • ret.push_back(curr->val)
      • pushLarger(curr->right, larger, target)
  • ret ফেরত

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector 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 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 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 closestKValues(TreeNode* root, double target, int k) {
        vector ret;
        stack smaller;
        stack 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& st, double target) {
        while (node) {
            if (node->val < target) {
                st.push(node);
                node = node->right;
            } else {
                node = node->left;
            }
        }
    }
    void pushLarger(TreeNode* node, stack& st, double target) {
        while (node) {
            if (node->val >= target) {
                st.push(node);
                node = node->left;
            } else {
                node = node->right;
            }
        }
    }
};

int main() {
    Solution ob;
    vector 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]