C++ এ একটি সুষম BST-এ প্রদত্ত যোগফল সহ একটি জোড়া খুঁজুন

ধরুন আমাদের একটি সুষম বাইনারি সার্চ ট্রি এবং একটি টার্গেট যোগফল আছে, আমাদেরকে একটি পদ্ধতি নির্ধারণ করতে হবে যা চেক করে যে এটি টার্গেট যোগফলের সমতুল্য যোগফলের সাথে একটি জোড়া কিনা। এক্ষেত্রে. আমাদের মনে রাখতে হবে যে বাইনারি সার্চ ট্রি অপরিবর্তনীয়।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে (9 + 26 =35)

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্যাক s1, s2 সংজ্ঞায়িত করুন
• done1 :=false, done2 ​​:=false
• val1 :=0, val2 :=0
• curr1 :=root, curr2 :=root
• অসীম লুপ, কর −
  • যখন সম্পন্ন1 মিথ্যা, −
    করুন
    • যদি curr1 NULL এর সমান না হয়, তাহলে &minus
      • s1-এ curr1 ঢোকান
      • curr1 :=curr1 এর বাম
    • অন্যথায়
      • যদি s1 খালি হয়, তাহলে −
        • সম্পন্ন1 :=1
      • অন্যথায়
        • curr1 :=s1 এর শীর্ষ উপাদান
        • s1 থেকে উপাদান মুছুন
        • val1 :=curr1 এর val
        • curr1 :=curr1 এর ডানদিকে
        • সম্পন্ন1 :=1
  • যখন done2 ​​মিথ্যা, −
    করুন
    • যদি curr2 NULL এর সমান না হয়, তাহলে −
      • s2-এ curr2 ঢোকান
      • curr2 :=curr2 এর ডানদিকে
    • অন্যথায়
      • যদি s2 খালি হয়, তাহলে −
        • done2 ​​:=1
    • অন্যথায়
      • curr2 :=s2 এর শীর্ষ উপাদান
      • s2 থেকে উপাদান মুছুন
      • val2 :=curr2 এর val
      • curr2 :=curr2 এর বাম
      • done2 ​​:=1
  • যদি val1 val2 এর সমান না হয় এবং (val1 + val2) টার্গেটের সমান হয়, তাহলে −
    • প্রিন্ট পেয়ার (val1 + val2 =টার্গেট)
    • সত্য ফেরত দিন
  • অন্যথায় যখন (val1 + val2) <লক্ষ্য, তারপর −
    • done1 :=মিথ্যা
  • অন্যথায় যখন (val1 + val2)> লক্ষ্য, তারপর −
    • done2 ​​:=মিথ্যা
  • যদি val1>=val2 হয়, তাহলে −
    • মিথ্যে ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100
class TreeNode {
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data) {
         val = data;
         left = NULL;
         right = NULL;
      }
};
bool isPairPresent(TreeNode* root, int target) {
   stack<TreeNode*> s1, s2;
   bool done1 = false, done2 = false;
   int val1 = 0, val2 = 0;
   TreeNode *curr1 = root, *curr2 = root;
   while (true) {
      while (done1 == false) {
         if (curr1 != NULL) {
            s1.push(curr1);
            curr1 = curr1->left;
         }
         else {
            if (s1.empty())
               done1 = 1;
            else {
               curr1 = s1.top();
               s1.pop();
               val1 = curr1->val;
               curr1 = curr1->right;
               done1 = 1;
            }
         }
      }
      while (done2 == false) {
         if (curr2 != NULL) {
            s2.push(curr2);
            curr2 = curr2->right;
         }
         else {
            if (s2.empty())
               done2 = 1;
            else {
               curr2 = s2.top();
               s2.pop();
               val2 = curr2->val;
               curr2 = curr2->left;
               done2 = 1;
            }
         }
      }
      if ((val1 != val2) && (val1 + val2) == target) {
         cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
         return true;
      }
      else if ((val1 + val2) < target)
         done1 = false;
      else if ((val1 + val2) > target)
         done2 = false;
      if (val1 >= val2)
         return false;
   }
}
int main() {
   TreeNode* root = new TreeNode(16);
   root->left = new TreeNode(11);
   root->right = new TreeNode(21);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(13);
   root->right->left = new TreeNode(17);
   root->right->right = new TreeNode(26);
   int target = 35;
   cout << (isPairPresent(root, target));
}

ইনপুট

TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);

আউটপুট

Pair Found: 9 + 26 = 35
1