मान लीजिए हमारे पास एक संतुलित बाइनरी सर्च ट्री है, हमें is_valid_triplet() नामक एक फ़ंक्शन बनाना है जो तब सच लौटाता है जब दिए गए BST में एक ट्रिपलट मौजूद हो जिसका योग 0 के बराबर हो, अन्यथा गलत लौटाता है। इन बाधाओं का पालन करके विधि डिज़ाइन करें −
<उल क्लास="सूची"><ली>अपेक्षित समय जटिलता O(n^2) है
<ली>O(logn) अतिरिक्त स्थान का उपयोग किया जा सकता है।
तो, यदि इनपुट इस तरह है
तो आउटपुट True होगा, क्योंकि ट्रिपलट है [-15,7,8]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
<उल क्लास="सूची"><ली>bst_to_doubli_list() नामक एक फ़ंक्शन परिभाषित करें, यह रूट, हेड, टेल लेगा,
<ली>यदि रूट NULL के समान है, तो −
<उल क्लास="सूची"><ली>लौटें
<ली>यदि रूट का बायां भाग null नहीं है, तो −
<उल क्लास="सूची"><ली>bst_to_doubli_list(रूट का बायां, हेड, टेल)
<ली>रूट का बायां := टेल
<ली>यदि टेल null नहीं है, तो −
<उल क्लास="सूची"><ली>टेल का दायां := रूट
<ली>अन्यथा
<उल क्लास="सूची"><ली>हेड := रूट
<ली>टेल := रूट
<ली>यदि रूट का दायां भाग null नहीं है, तो −
<उल क्लास="सूची"><ली>bst_to_doubli_list(रूट का दायां, हेड, टेल)
<ली>is_in_double_list() नामक एक फ़ंक्शन परिभाषित करें, यह हेड, टेल, योग लेगा,
<ली>जब तक हेड टेल के बराबर नहीं है, तब तक करें −
<उल क्लास="सूची"><ली>वर्तमान := हेड की कुंजी + टेल की कुंजी
<ली>यदि वर्तमान योग के समान है, तो −
<उल क्लास="सूची"><ली>सच लौटाएं
<ली>अन्यथा जब वर्तमान > योग, तो −
<उल क्लास="सूची"><ली>टेल := टेल का बायां
<ली>अन्यथा
<उल क्लास="सूची"><ली>हेड := हेड का दायां
<ली>गलत लौटाएं
<ली>मुख्य विधि से, निम्नलिखित करें −
<ली>यदि रूट null है, तो −
<उल क्लास="सूची"><ली>गलत लौटाएं
<ली>हेड = null
<ली>टेल = null
<ली>bst_to_doubli_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);
आउटपुट
1
