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

मान लीजिए कि हमारे पास दो ट्रैवर्सल अनुक्रम हैं प्रीऑर्डर और पोस्टऑर्डर, हमें इन दो अनुक्रमों से बाइनरी ट्री उत्पन्न करना है। तो अगर अनुक्रम [1,2,4,5,3,6,7], [4,5,2,6,7,3,1] हैं, तो आउटपुट होगा

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

• उत्तर:=पूर्व [0] मान लेकर एक ट्री नोड बनाएं, स्टैक:=खाली स्टैक, और उत्तर डालें
• i :=1 और j :=0
• जबकि मैं <पूर्व की लंबाई और j <पोस्ट की लंबाई
  • यदि स्टैक का शीर्ष मान =पोस्ट[j] है, तो j को 1 से बढ़ाएं, स्टैक से पॉप करें, और अगले पुनरावृत्ति के लिए जाएं
  • नोड :=पूर्व [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,]