Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

संतुलित BST में दिए गए योग वाली जोड़ी खोजें C++ में


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

उदाहरण के लिए, यदि इनपुट इस तरह का है:

संतुलित BST में दिए गए योग वाली जोड़ी खोजें C++ में

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

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

  • दो स्टैक s1, s2 परिभाषित करें
  • done1 := false, done2 := false
  • val1 := 0, val2 := 0
  • curr1 := root, curr2 := root
  • अनंत लूप में, निम्न कार्य करें:
    • जब done1 false हो:
      • यदि curr1 NULL नहीं है, तो:
        • curr1 को s1 में डालें
        • curr1 := curr1 का बायां बच्चा
      • अन्यथा:
        • यदि s1 खाली है, तो done1 := true
        • अन्यथा:
          • curr1 := s1 का शीर्ष तत्व
          • s1 से तत्व हटाएं
          • val1 := curr1 का मान
          • curr1 := curr1 का दायां बच्चा
          • done1 := true
    • जब done2 false हो:
      • यदि curr2 NULL नहीं है, तो:
        • curr2 को s2 में डालें
        • curr2 := curr2 का दायां बच्चा
      • अन्यथा:
        • यदि s2 खाली है, तो done2 := true
        • अन्यथा:
          • curr2 := s2 का शीर्ष तत्व
          • s2 से तत्व हटाएं
          • val2 := curr2 का मान
          • curr2 := curr2 का बायां बच्चा
          • done2 := true
    • यदि val1 ≠ val2 और (val1 + val2) लक्ष्य के बराबर है, तो:
      • जोड़ी प्रिंट करें (val1 + val2 = लक्ष्य)
      • true लौटाएं
    • अन्यथा जब (val1 + val2) < लक्ष्य, तो done1 := false
    • अन्यथा जब (val1 + val2) > लक्ष्य, तो done2 := false
    • यदि val1 ≥ val2, तो false लौटाएं

उदाहरण

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

#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

  1. - C++ में दिए गए अंतर वाली जोड़ी ढूंढें

    समस्या विवरण एक सरणी A दी गई है जिसमें n विभिन्न तत्व हैं। हमें सरणी से एक जोड़ी (x, y) ढूंढनी है जिससे x और y का अंतर दिए गए अंतर d के बराबर हो। उदाहरण के लिए, यदि सरणी A = [10, 15, 26, 30, 40, 70] है और दिया गया अंतर 30 है, तो जोड़ियां (10, 40) और (30, 70) होंगी। हल दृष्टिकोण इस समस्या को हल करन

  1. - C++ में दिए गए GCD और LCM के साथ कोई भी पेयर खोजें

    इस सेक्शन में हम देखेंगे कि दिए गए GCD और LCM मानों का उपयोग करके नंबर पेयर्स की संख्या कैसे प्राप्त करें। मान लीजिए GCD और LCM मान 2 और 12 हैं। अब नंबरों के संभावित पेयर्स हैं (2, 12), (4, 6), (6, 4) और (12, 2)। इसलिए हमारा प्रोग्राम पेयर्स की संख्या ढूंढेगा। वह 4 है।आइए एल्गोरिदम देखें कि इस समस्य

  1. Java में बैलेंस्ड BST में दिए गए योग के साथ एक जोड़ी खोजें Java में बैलेंस्ड BST में दिए गए योग के साथ एक जोड़ी खोजें

    अवधारणाएक दिए गए बैलेंस्ड बाइनरी सर्च ट्री और एक टारगेट योग के संबंध में, हम एक फ़ंक्शन लिखते हैं जो true वापस करता है यदि कोई जोड़ी है जिसका योग टारगेट योग के बराबर है, अन्यथा false वापस करता है। इस मामले में, अपेक्षित समय जटिलता O(n) है और केवल O(log n) अतिरिक्त स्पेस लागू किया जा सकता है। यहां, ब