मान लीजिए कि हमारे पास बाइनरी सर्च ट्री (BST) का प्रीऑर्डर ट्रैवर्सल है। हमें यह जांचना होगा कि प्रत्येक आंतरिक नोड में केवल एक बच्चा है या नहीं।
इसलिए, यदि इनपुट प्रीऑर्डर =[22, 12, 13, 15, 14] जैसा है, तो आउटपुट सही होगा क्योंकि बीएसटी जैसा है -
इसे हल करने के लिए, हम एक कुशल दृष्टिकोण का पालन कर सकते हैं। चूंकि नोड के सभी मृतक या तो छोटे या बड़े होते हैं, तो हम इन चरणों का पालन कर सकते हैं -
-
नोड का अगला अग्रिम-आदेश उत्तराधिकारी प्राप्त करें
-
नोड का अंतिम अग्रिम-आदेश उत्तराधिकारी प्राप्त करें
-
अब जब दोनों उत्तराधिकारी वर्तमान नोड से कम या अधिक हों तो दोबारा जांचें अन्यथा झूठी वापसी करें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- अगला:=0, अंतिम:=0
- i के लिए 0 से प्रीऑर्डर के आकार के लिए - 1, do
- अगला:=अग्रिम आदेश[i] - अग्रिम आदेश[i+1]
- अंतिम:=अग्रिम आदेश[i] - अग्रिम आदेश का अंतिम मान
- यदि अगला * अंतिम <0, तो
- झूठी वापसी
- सही लौटें
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
def solve(preorder): next = 0 last = 0 for i in range(len(preorder)-1): next = preorder[i] - preorder[i+1] last = preorder[i] - preorder[-1] if next * last < 0: return False return True preorder = [22, 12, 13, 15, 14] print(solve(preorder))
इनपुट
[22, 12, 13, 15, 14]
आउटपुट
True