পাইথনে প্রিঅর্ডার ট্রাভার্সাল থেকে বাইনারি সার্চ ট্রি তৈরি করুন

ধরুন আমাদের একটি বাইনারি সার্চ ট্রি তৈরি করতে হবে যা প্রদত্ত প্রিঅর্ডার ট্রাভার্সালের সাথে মেলে। তাই যদি প্রি-অর্ডার ট্রাভার্সাল [8,5,1,7,10,12] এর মত হয়, তাহলে আউটপুট হবে [8,5,10,1,7,null,12], তাই ট্রি হবে −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• root :=0 ^th প্রি-অর্ডার ট্রাভার্সাল তালিকার নোড
• স্ট্যাক :=একটি স্ট্যাক, এবং স্ট্যাকের মধ্যে রুট পুশ করুন
• প্রি-অর্ডার তালিকার দ্বিতীয় উপাদান থেকে i প্রতিটি উপাদানের জন্য
  • 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]