दो योग IV - इनपुट C++ में एक BST है

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक लक्ष्य मान है; हमें यह जांचना होगा कि क्या बीएसटी में दो तत्व मौजूद हैं जैसे कि उनका योग दिए गए लक्ष्य के बराबर है या नहीं।

तो, अगर इनपुट पसंद है

तो आउटपुट ट्रू होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सरणी को परिभाषित करें v

• एक फ़ंक्शन इनऑर्डर () को परिभाषित करें, यह रूट लेगा,

• यदि रूट शून्य है, तो -

  • वापसी

• इनऑर्डर (रूट के बाएं)

• v

  . में रूट का मान डालें

• इनऑर्डर (रूट के बाएं)

• फ़ंक्शन फाइंडनोड () को परिभाषित करें, इसमें k लगेगा,

• n:=वी का आकार

• जबकि मैं <जे, करता हूं -

  • टी:=वी[i] + वी[जे]

  • यदि t, k के समान है, तो -

    • सही लौटें

  • यदि टी <के, तो -

    • (मैं 1 से बढ़ाइए)

  • अन्यथा

    • (j को 1 से घटाएं)

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• इनऑर्डर (रूट)

• सरणी को क्रमबद्ध करें v

• रिटर्न फाइंडनोड (के)

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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