สมมติว่าเรามีแผนผังการค้นหาแบบไบนารีและค่าเป้าหมาย เราต้องหาค่า k ใน BST นั้นที่ใกล้กับเป้าหมายมากที่สุด เราต้องจำไว้ว่าค่าเป้าหมายเป็นตัวเลขทศนิยม เราสามารถสมมติได้ว่า k ถูกต้องเสมอ และ k ≤ โหนดทั้งหมด
ดังนั้นหากอินพุตเป็นแบบ
เป้าหมาย =3.714286 และ k =2 จากนั้นผลลัพธ์จะเป็น [4,3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน pushSmaller() ซึ่งจะใช้ node,stack st และ target
-
ในขณะที่ไม่มีโหนด ให้ทำ -
-
ถ้า val ของโหนด <เป้าหมาย แล้ว −
-
แทรกโหนดลงใน st
-
โหนด :=ด้านขวาของโหนด
-
-
มิฉะนั้น
-
โหนด :=ด้านซ้ายของโหนด
-
-
-
กำหนดฟังก์ชัน pushLarger() ซึ่งจะรับ node, stack st, target
-
ขณะที่โหนดว่าง ให้ทำ -
-
ถ้า val ของโหนด>=เป้าหมาย แล้ว −
-
แทรกโหนดลงใน st
-
โหนด :=ด้านซ้ายของโหนด
-
-
มิฉะนั้น
-
โหนด :=ด้านขวาของโหนด
-
-
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดอาร์เรย์ ret
-
กำหนดหนึ่งกองที่เล็กกว่า
-
กำหนดหนึ่งกองที่ใหญ่ขึ้น
-
pushLarger(รูท ใหญ่กว่า เป้าหมาย)
-
pushSmaller(รูท เล็กกว่า เป้าหมาย)
-
ในขณะที่ k ไม่ใช่ศูนย์ ให้ลด k ในแต่ละขั้นตอน ทำ -
-
ถ้าเล็กกว่าไม่ว่างเปล่าและ (ขนาดใหญ่กว่าว่างเปล่าหรือ |target - ค่าขององค์ประกอบด้านบนของที่เล็กกว่า| <|เป้าหมาย - องค์ประกอบด้านบนของขนาดใหญ่กว่า|)
-
curr =องค์ประกอบด้านบนของที่เล็กกว่า
-
ลบองค์ประกอบออกจากที่เล็กกว่า
-
ใส่ val ของ curr ที่ส่วนท้ายของ ret
-
pushSmaller(ซ้ายของสกุลเงิน เล็กกว่า เป้าหมาย)
-
-
มิฉะนั้น
-
curr =องค์ประกอบด้านบนของที่ใหญ่กว่า
-
ลบองค์ประกอบออกจากที่ใหญ่กว่า
-
ใส่ val ของ curr ที่ส่วนท้ายของ ret
-
pushSmaller(ด้านขวาของสกุลเงิน, ใหญ่กว่า, เป้าหมาย)
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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, ]
