हमारे पास एक सरणी ए है, हमें यह जांचना होगा कि सरणी एन स्तरों के साथ बीएसटी का प्रतिनिधित्व कर सकती है या नहीं। जैसा कि स्तर है, हम निम्नलिखित तरीके से एक पेड़ का निर्माण कर सकते हैं। मान लें कि कोई संख्या k है, k से बड़ा मान दाईं ओर जाता है, और k से कम बाईं ओर चलता है। मान लीजिए कि दो सूचियाँ हैं:{50, 20, 9, 25, 10}, और {50, 30, 20, 25, 10}
पहला मान्य नहीं है, लेकिन दूसरा मान्य है।
इसे जांचने के लिए हम या तो बीएसटी बना सकते हैं और ऊंचाई की जांच कर सकते हैं, अन्यथा सरणी आधारित दृष्टिकोण का उपयोग करें। सरणी आधारित दृष्टिकोण नीचे जैसा है -
- बाएं सबट्री की अधिकतम सीमा को चिह्नित करने के लिए दो चर अधिकतम =अनंत, और दाएं उपट्री के लिए न्यूनतम सीमा को चिह्नित करने के लिए न्यूनतम =नकारात्मक अनंत लें
- गिरफ्तारी [i] से गिरफ्तार [n - 1] तक के प्रत्येक तत्व के लिए, निम्न चरणों को दोहराएं
- अगर गिरफ्तारी [i]> गिरफ्तारी [i - 1] और गिरफ्तारी [i]> मिनट और गिरफ्तारी [i] <अधिकतम, फिर न्यूनतम अपडेट करें:=गिरफ्तारी [i - 1]
- अन्यथा अगर गिरफ्तारी [i]> मिनट और गिरफ्तारी [i] <अधिकतम, तो अधिकतम अपडेट करें:=गिरफ्तारी [i]
- यदि इनमें से कोई भी मान्य नहीं है, तो तत्व को एक नए स्तर में सम्मिलित किया जाएगा, इसलिए तोड़ें
उदाहरण
#include <iostream>
using namespace std;
bool canMakeBSTifHeightN(int arr[], int n) {
int min = INT_MIN;
int max = INT_MAX;
for(int i = 1; i < n; i++){
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
min = arr[i - 1];
} else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] <
max) {
max = arr[i - 1];
} else {
return true;
}
}
return false;
}
int main() {
int elements[] = {50, 30, 20, 25, 10};
int n = sizeof(elements)/sizeof(elements[0]);
if (canMakeBSTifHeightN(elements, n))
cout << "We can make BST of height " << n;
else
cout << "We can not make BST of height " << n;
} आउटपुट
We can make BST of height 5