C++의 이진 검색 트리에서 가장 가까운 요소 찾기

하나의 이진 검색 트리(BST)와 다른 대상 값이 있다고 가정합니다. 주어진 BST에서 목표에 가장 가까운 k 값을 찾아야 합니다. 여기서 목표 값은 부동 소수점 숫자입니다. k는 항상 유효하고 k ≤ 총 노드라고 가정할 수 있습니다.

따라서 입력이 다음과 같으면

target =3.714286, k =2이면 출력은 [4,3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• pushSmaller() 함수를 정의하면 node,stack st 및 target이 사용됩니다.

• 노드가 없는 동안 수행 -

  • 노드의 val이

    • 노드를 st

      에 삽입

    • 노드 :=노드의 오른쪽

  • 그렇지 않으면

    • 노드 :=노드의 왼쪽

• pushLarger() 함수를 정의하면 node, stack st, target,

  가 사용됩니다.

• 노드가 비어 있는 동안 수행 -

  • 노드의 val>=target이면 -

    • 노드를 st

      에 삽입

    • 노드 :=노드의 왼쪽

  • 그렇지 않으면

    • 노드 :=노드의 오른쪽

• 주요 방법에서 다음을 수행하십시오 -

• ret 배열 정의

• 한 스택 더 작게 정의

• 한 스택 더 크게 정의

• pushLarger(루트, 더 큼, 대상)

• pushSmaller(루트, 더 작은, 대상)

• k가 0이 아닌 동안 각 단계에서 k를 감소시키고 -

  • 작은 것이 비어 있지 않고 (큰 것이 비어 있거나 |target - 작은 것의 맨 위 요소 값| <|target - 큰 것의 맨 위 요소|)

    • curr =더 작은 것의 최상위 요소

    • 더 작은 것에서 요소 삭제

    • ret의 끝에 curr의 val 삽입

    • pushSmaller(커서 왼쪽, 더 작게, 대상)

  • 그렇지 않으면

    • curr =더 큰 것의 최상위 요소

    • 더 큰 요소에서 삭제

    • ret의 끝에 curr의 val 삽입

    • pushSmaller(커서 오른쪽, 크게, 대상)

• 리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   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, ]