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

ধরুন আমাদের দুটি ট্রাভার্সাল সিকোয়েন্স প্রিঅর্ডার এবং পোস্টঅর্ডার আছে, আমাদের এই দুটি সিকোয়েন্স থেকে বাইনারি ট্রি তৈরি করতে হবে। সুতরাং যদি ক্রমগুলি [1,2,4,5,3,6,7], [4,5,2,6,7,3,1] হয়, তাহলে আউটপুট হবে

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

• উত্তর :=মান প্রি[0] নিয়ে একটি ট্রি নোড তৈরি করুন, স্ট্যাক :=খালি স্ট্যাক, এবং উত্তর সন্নিবেশ করুন
• i :=1 এবং j :=0
• যখন i <পূর্বের দৈর্ঘ্য এবং j <পোস্টের দৈর্ঘ্য
  • যদি স্ট্যাকের শীর্ষ মান =post[j] হয়, তাহলে j 1 দ্বারা বাড়ান, স্ট্যাক থেকে পপ করুন এবং পরবর্তী পুনরাবৃত্তির জন্য যান
  • নোড :=মান pre[i]
  সহ একটি ট্রি নোড তৈরি করুন
  • স্ট্যাক টপ নোডের বাম অংশ খালি থাকলে, স্ট্যাক টপ নোডের বাঁদিকে নোড হিসেবে সেট করুন, অন্যথায় স্ট্যাক টপ নোডের ডানদিকে নোড হিসেবে সেট করুন
  • স্ট্যাকের মধ্যে নোড ঢোকান
  • i 1 দ্বারা বাড়ান
• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def height(root):
   if root is None:
      return 0
   else :
      # Compute the height of left and right subtree
      l_height = height(root.left)
      r_height = height(root.right)
      #Find the greater one, and return it
      if l_height > r_height :
         return l_height+1
      else:
         return r_height+1
def print_given_level(root, level):
   if root is None:
      return
   if level == 1:
      print(root.data,end = ',')
   elif level > 1 :
      print_given_level(root.left , level-1)
      print_given_level(root.right , level-1)
def level_order(root):
   print('[', end = '')
   h = height(root)
   for i in range(1, h+1):
      print_given_level(root, i)
   print(']')
class Solution(object):
   def constructFromPrePost(self, pre, post):
      """
      :type pre: List[int]
      :type post: List[int]
      :rtype: TreeNode
      """
      ans = TreeNode(pre[0])
      stack = [ans]
      i = 1
      j = 0
      while i < len(pre) and j < len(post):
         if stack[-1].data == post[j]:
            j+=1
            stack.pop(-1)
            continue
         node = TreeNode(pre[i])
         if not stack[-1].left:
            stack[-1].left = node
         else:
            stack[-1].right = node
            stack.append(node)
            i+=1
   return ans
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree)

ইনপুট

[1,2,4,5,3,6,7]
[4,5,2,6,7,3,1]
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]

আউটপুট

[1,2,3,4,5,6,7,]