C++ में BST प्रीऑर्डर अनुक्रम सत्यापित करें - स्टैक-आधारित O(n) समाधान

समस्या विवरण

मान लीजिए हमारे पास संख्याओं का एक अनुक्रम है; हमें जांचना है कि क्या यह बाइनरी सर्च ट्री का सही प्रीऑर्डर ट्रैवर्सल अनुक्रम है। हम मान सकते हैं कि अनुक्रम में प्रत्येक संख्या अद्वितीय है।

उदाहरण के लिए, यदि इनपुट [5,2,1,3,6] है, तो आउटपुट true होगा।

समाधान दृष्टिकोण

स्टैक सिमुलेशन + निचली सीमा ट्रैकिंग:

1. itr := -1 (स्टैक शीर्ष सूचकांक)
2. low := -अनंत (निचली सीमा)
3. i को 0 से प्रीऑर्डर आकार-1 तक:
   • x := preorder[i]
   • यदि x < low, तो false लौटाएं
   • जब (itr >= 0 और preorder[itr] < x):
     • low := preorder[itr]
     • itr--
   • itr++
   • preorder[itr] := x (वर्तमान को स्टैक पर पुश करें)
4. true लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    bool verifyPreorder(vector<int>& preorder) { 
        int itr = -1; 
        int low = INT_MIN; 
        for (int i = 0; i < preorder.size(); i++) { 
            int x = preorder[i]; 
            if (x < low) 
                return false; 
            while (itr >= 0 && preorder[itr] < x) { 
                low = preorder[itr]; 
                itr--; 
            } 
            itr++; 
            preorder[itr] = x; 
        } 
        return true; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {5,2,1,3,6}; 
    cout << (ob.verifyPreorder(v)); 
    return 0;
}

इनपुट

{5,2,1,3,6}

आउटपुट

1