ค่าที่ใกล้ที่สุดในต้นไม้ค้นหาไบนารี II ใน C++

สมมติว่าเรามีต้นไม้ค้นหาไบนารี (BST) และค่าเป้าหมาย (target) เราต้องหา k ค่าใน BST ที่ใกล้ที่สุดกับ target target เป็นทศนิยม k เสมอถูกต้องและ k ≤ จำนวนโหนดทั้งหมด

เช่น ถ้าอินพุตเป็นต้นไม้ตามรูป target = 3.714286, k = 2 ผลลัพธ์จะเป็น [4,3]

ในการแก้ปัญหานี้ เราจะใช้ 2 Stack เก็บโหนดที่น้อยกว่าและมากกว่า target ทำตามขั้นตอน:

• pushSmaller(node, st, target): while node: ถ้า node->val < target: push node, node = node->right; มิฉะนั้น node = node->left
• pushLarger(node, st, target): while node: ถ้า node->val >= target: push node, node = node->left; มิฉะนั้น node = node->right
• main: เรียก pushLarger และ pushSmaller จาก root; while k--: เปรียบเทียบ top ของ smaller และ larger ใกล้ target กว่ากัน นำค่านั้นใส่ผลลัพธ์ แล้ว push ต่อไป (smaller->left หรือ larger->right)

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector v){
    cout << "[";
    for(int i=0;i 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 closestKValues(TreeNode* root, double target, int k) {
        vector ret;
        stack 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;
    }
    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;
        }
    }
};
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]