पता लगाएं कि क्या संतुलित बीएसटी में कोई ट्रिपल है जो सी ++ में शून्य में जोड़ता है

मान लीजिए कि हमारे पास एक संतुलित बाइनरी सर्च ट्री है, हमें is_valid_triplet() नाम का एक फंक्शन बनाना होगा, जो तब सही हो जाता है जब दिए गए BST में एक ट्रिपलेट मौजूद होता है, जिसका योग 0 के बराबर होता है, अन्यथा गलत रिटर्न देता है। . इन बाधाओं का पालन करके विधि डिजाइन करें -

अपेक्षित समय जटिलता O(n^2)
. है
O(logn) अतिरिक्त स्थान का उपयोग किया जा सकता है।

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

तो आउटपुट ट्रू होगा, क्योंकि ट्रिपलेट [-15,7,8]

. है

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

फ़ंक्शन को परिभाषित करें bst_to_douli_list(), यह रूट, हेड, टेल,
लेगा
यदि रूट NULL के समान है, तो -
- वापसी
यदि रूट का बायां भाग शून्य नहीं है, तो -
- bst_to_douli_list (जड़, सिर, पूंछ के बाईं ओर)
जड़ के बाईं ओर :=पूंछ
अगर पूंछ शून्य नहीं है, तो -
- पूंछ का दाहिना भाग :=जड़
अन्यथा
- सिर :=जड़
पूंछ :=जड़
यदि मूल का दायाँ अशक्त नहीं है, तो -
- bst_to_douli_list (जड़, सिर, पूंछ के दाईं ओर)
फ़ंक्शन को परिभाषित करें is_in_double_list(), इसमें शीर्ष, पूंछ, योग,
. लगेगा
जबकि सिर पूंछ के बराबर नहीं है, करें -
- करंट:=सिर की कुंजी + पूंछ की कुंजी
- यदि धारा योग के समान है, तो -
  - सही लौटें
- अन्यथा जब करंट> योग, तब -
  - पूंछ:=पूंछ के बाईं ओर
- अन्यथा
  - सिर :=सिर के दायें
झूठी वापसी
मुख्य विधि से, निम्न कार्य करें -
यदि रूट शून्य है, तो -
- झूठी वापसी
सिर =शून्य
पूंछ =शून्य
bst_to_douli_list(जड़, सिर, पूंछ)
जबकि (सिर का दाहिना भाग पूंछ के बराबर नहीं है और सिर की कुंजी <0), करते हैं -
- अगर is_in_double(सिर का दायां, पूंछ, सिर की कुंजी * (-1), तो
  - सही लौटें
- अन्यथा
  - सिर :=सिर के दायें
झूठी वापसी

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int key;
   TreeNode *left;
   TreeNode *right;
   TreeNode() : key(0), left(NULL), right(NULL) {}
   TreeNode(int x) : key(x), left(NULL), right(NULL) {}
};
void bst_to_doubli_list(TreeNode* root, TreeNode** head, TreeNode** tail) {
   if (root == NULL)
      return;
   if (root->left)
      bst_to_doubli_list(root->left, head, tail);
   root->left = *tail;
   if (*tail)
      (*tail)->right = root;
   else
      *head = root;
      *tail = root;
   if (root->right)
      bst_to_doubli_list(root->right, head, tail);
}
bool is_in_double_list(TreeNode* head, TreeNode* tail, int sum) {
   while (head != tail) {
      int current = head->key + tail->key;
      if (current == sum)
         return true;
      else if (current > sum)
         tail = tail->left;
      else
         head = head->right;
   }
   return false;
}
bool is_valid_triplet(TreeNode *root) {
   if (root == NULL)
      return false;
   TreeNode* head = NULL;
   TreeNode* tail = NULL;
   bst_to_doubli_list(root, &head, &tail);
   while ((head->right != tail) && (head->key < 0)){
      if (is_in_double_list(head->right, tail, -1*head->key))
         return true;
      else
         head = head->right;
   }
   return false;
}
TreeNode* insert(TreeNode* root, int key) {
   if (root == NULL)
      return new TreeNode(key);
   if (root->key > key)
      root->left = insert(root->left, key);
   else
      root->right = insert(root->right, key);
   return root;
}
int main(){
   TreeNode* root = NULL;
   root = insert(root, 7);
   root = insert(root, -15);
   root = insert(root, 15);
   root = insert(root, -7);
   root = insert(root, 14);
   root = insert(root, 16);
   root = insert(root, 8);
   cout << is_valid_triplet(root);
}

इनपुट

root = insert(root, 7);
root = insert(root, -15);
root = insert(root, 15);
root = insert(root, -7);
root = insert(root, 14);
root = insert(root, 16);
root = insert(root, 8);