Two Sum IV - C++에서 입력은 BST입니다.

이진 검색 트리와 하나의 대상 값이 있다고 가정합니다. BST에 두 요소의 합이 주어진 목표와 같도록 존재하는지 여부를 확인해야 합니다.

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

그러면 출력이 True가 됩니다.

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

• 배열 정의 v

• inorder() 함수를 정의하면 루트가 됩니다.

• 루트가 null이면 -

  • 반환

• inorder(루트의 왼쪽)

• 루트 값을 v

  에 삽입

• inorder(루트의 왼쪽)

• findnode() 함수를 정의하면 k가 필요합니다.

• n :=v의 크기

• i

  • t :=v[i] + v[j]

  • t가 k와 같으면 -

    • true를 반환

  • t

    • (i를 1씩 증가)

  • 그렇지 않으면

    • (j를 1만큼 감소)

• 거짓을 반환

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

• inorder(루트)

• 배열 v

  정렬

• findnode(k) 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
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> v;
   void inorder(TreeNode* root){
      if (root == NULL || root->val == 0)
         return;
      inorder(root->left);
      v.push_back(root->val);
      inorder(root->right);
   }
   bool findnode(int k){
      int n = v.size(), i = 0, j = n - 1;
      while (i < j) {
         int t = v[i] + v[j];
         if (t == k)
            return true;
         if (t < k)
            i++;
         else
            j--;
      }
      return false;
   }
   bool findTarget(TreeNode* root, int k){
      inorder(root);
      sort(v.begin(), v.end());
      return findnode(k);
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,6,2,4,NULL,7};
   TreeNode *root = make_tree(v);
   cout << (ob.findTarget(root, 9));
}

입력

{5,3,6,2,4,NULL,7},9

출력

1