पायथन में प्रीऑर्डर ट्रैवर्सल से बाइनरी सर्च ट्री बनाएं

मान लीजिए हमें एक बाइनरी सर्च ट्री बनाना है जो दिए गए प्रीऑर्डर ट्रैवर्सल से मेल खाता हो। इसलिए यदि प्री-ऑर्डर ट्रैवर्सल [8,5,1,7,10,12] जैसा है, तो आउटपुट [8,5,10,1,7,null,12] होगा, इसलिए ट्री होगा -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• root := प्रीऑर्डर ट्रैवर्सल लिस्ट का 0वां नोड
• stack := एक स्टैक, और रूट को स्टैक में पुश करें
• प्रीऑर्डर लिस्ट के दूसरे एलिमेंट से प्रत्येक एलिमेंट i के लिए
  • i := मान i वाला एक नोड
  • यदि i का मान स्टैक के टॉप एलिमेंट से कम है, तो
    • स्टैक टॉप नोड का बायां := i
    • i को स्टैक में इन्सर्ट करें
  • अन्यथा
    • जब तक स्टैक खाली नहीं है, और स्टैक टॉप एलिमेंट का मान i के मान से कम है
      • last := स्टैक का टॉप
      • स्टैक से एलिमेंट पॉप करें
    • last नोड का दायां := i
    • i को स्टैक में इन्सर्ट करें
• root लौटाएं

उदाहरण

class Solution(object):
    def bstFromPreorder(self, preorder):
        \"\"\"
        :type preorder: List[int]
        :rtype: TreeNode
        \"\"\"
        root = TreeNode(preorder[0])
        stack = [root]
        for i in preorder[1:]:
            i = TreeNode(i)
            if i.val
इनपुट
[8,5,1,7,10,12]
आउटपुट
[8,5,10,1,7,null,12]