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

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

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

• रूट:=0 ^वें प्रीऑर्डर ट्रैवर्सल सूची का नोड
• स्टैक:=एक स्टैक, और स्टैक में रूट पुश करें
• प्रीआर्डर सूची के दूसरे तत्व से प्रत्येक तत्व के लिए
  • i :=एक नोड जिसका मान i
  . है
  • यदि i का मान <स्टैक शीर्ष तत्व के शीर्ष पर है, तो
    • स्टैक टॉप नोड के बाईं ओर:=i
    • i को स्टैक में डालें
  • अन्यथा
    • जबकि स्टैक खाली नहीं है, और स्टैक शीर्ष तत्व मान
    • अंतिम:=स्टैक में सबसे ऊपर
    • स्टैक से पॉप तत्व
  • अंतिम नोड के दाईं ओर:=i
  • i को स्टैक में डालें

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<stack[-1].val:
            stack[-1].left = i
            stack.append(i)
         else:
            while stack and stack[-1].val<i.val:
               last = stack.pop(-1)
            last.right = i
            stack.append(i)
      return root

[8,5,1,7,10,12]

[8,5,10,1,7,null,12]