C++ में संतुलित BST में दिए गए योग के साथ एक युग्म खोजें

मान लीजिए कि हमारे पास एक संतुलित बाइनरी सर्च ट्री और एक लक्ष्य योग है, हमें एक ऐसी विधि को परिभाषित करना होगा जो यह जांचती है कि यह योग के साथ एक जोड़ी लक्ष्य योग के बराबर है या नहीं। इस मामले में। हमें यह ध्यान रखना होगा कि बाइनरी सर्च ट्री अपरिवर्तनीय है।

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

तो आउटपुट होगा (9 + 26 =35)

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

• स्टैक s1, s2 परिभाषित करें
• किया गया1:=झूठा, किया हुआ2:=झूठा
• val1 :=0, val2 :=0
• curr1 :=root, curr2 :=root
• अनंत लूप, करो −
  • जबकि किया1 गलत है, करें −
    • यदि curr1 NULL के बराबर नहीं है, तो &माइनस
      • कर1 को s1 में डालें
      • curr1 :=curr1 के बाएँ
    • अन्यथा
      • यदि s1 खाली है, तो −
        • किया गया1 :=1
      • अन्यथा
        • curr1 :=s1 का शीर्ष तत्व
        • s1 से तत्व हटाएं
        • val1:=curr1 का वैल
        • curr1 :=curr1 का दायां
        • किया गया1 :=1
  • जबकि किया हुआ2 गलत है, करें −
    • यदि curr2 NULL के बराबर नहीं है, तो −
      • कर2 को s2 में डालें
      • curr2 :=curr2 का अधिकार
    • अन्यथा
      • यदि s2 खाली है, तो −
        • किया गया2:=1
    • अन्यथा
      • curr2 :=s2 का शीर्ष तत्व
      • s2 से तत्व हटाएं
      • val2 :=curr2 का वैल
      • curr2 :=curr2 के बाएँ
      • किया गया2:=1
  • यदि val1 val2 के बराबर नहीं है और (val1 + val2) लक्ष्य के समान है, तो −
    • प्रिंट जोड़ी (val1 + val2 =लक्ष्य)
    • सही लौटें
  • अन्यथा जब (val1 + val2) <लक्ष्य, तब −
    • किया गया1:=झूठा
  • अन्यथा जब (val1 + val2)> लक्ष्य, तब −
    • किया गया2:=झूठा
  • यदि 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