หา K ค่าที่ใกล้ Target มากที่สุดใน BST ใน C++

โจทย์: กำหนด BST และ target (float) หา k ค่าใน BST ที่ใกล้ target มากที่สุด (k ≤ total nodes)

ตัวอย่าง: BST [4,2,5,1,3], target=3.714286, k=2 → [4,3]

อัลกอริธึม: Two Stacks (Inorder + Reverse Inorder)

1. pushSmaller: ดึงค่าที่ < target เรียงมาก→น้อย (stack)
2. pushLarger: ดึงค่าที่ ≥ target เรียงน้อย→มาก (stack)
3. Merge: เปรียบเทียบ top ของทั้งสอง stack ดึงค่าที่ใกล้ target กว่า ทำซ้ำ k ครั้ง

ตัวอย่างโค้ด C++

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int d) : val(d), left(NULL), right(NULL) {}
};

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;
    }
};

int main() {
    // Build tree [4,2,5,1,3]...
    Solution ob;
    // print result
}

อินพุท

{4,2,5,1,3}, 3.7142, 2

เอาต์พุท

[4, 3]

Complexity

• Time: O(log N + K) average, O(N) worst case
• Space: O(log N) average (stack height)