पायथन में जांचें कि कोई ऐरे बाइनरी सर्च ट्री का इनऑर्डर ट्रैवर्सल है या नहीं

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

उदाहरण के लिए, यदि इनपुट nums = [5, 8, 15, 18, 20, 26, 39] है, तो आउटपुट True होगा क्योंकि यह निम्न BST का इनऑर्डर ट्रैवर्सल है:

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

बाइनरी सर्च ट्री का इनऑर्डर ट्रैवर्सल हमेशा सॉर्टेड क्रम में होता है। इसलिए हमें केवल यह जांचना है कि ऐरे सॉर्टेड (गैर-घटते क्रम में) है या नहीं।

एल्गोरिदम चरण:

1. size = len(nums)
2. यदि आकार 0 या 1 है, तो True लौटाएं
3. इंडेक्स 1 से size-1 तक प्रत्येक तत्व के लिए:
• यदि nums[i-1] > nums[i], तो False लौटाएं
4. True लौटाएं

पायथन कार्यान्वयन

def solve(nums):
    size = len(nums)
    if size == 0 or size == 1:
        return True
    for i in range(1, size):
        if nums[i-1] > nums[i]:
            return False
    return True

nums = [5, 8, 15, 18, 20, 26, 39]
print(solve(nums))  # True

इनपुट

[5, 8, 15, 18, 20, 26, 39]

आउटपुट

True

व्याख्या:

दिया गया ऐरे [5, 8, 15, 18, 20, 26, 39] सख्ती से बढ़ते क्रम में है, जो किसी BST के इनऑर्डर ट्रैवर्सल की विशेषता है।