Xây dựng cây nhị phân từ Traversal đặt hàng trước và đặt hàng sau bằng Python

Giả sử chúng ta có hai trình tự duyệt Preorder và Postorder, chúng ta phải tạo cây nhị phân từ hai trình tự này. Vì vậy, nếu các trình tự là [1,2,4,5,3,6,7], [4,5,2,6,7,3,1], thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=tạo một nút cây bằng cách lấy giá trị trước [0], stack:=trống ngăn xếp và chèn ans
• i:=1 và j:=0
• while i <độ dài của bài viết trước và j <độ dài bài đăng
  • nếu giá trị hàng đầu của ngăn xếp =post [j], sau đó tăng j lên 1, bật từ ngăn xếp và chuyển sang lần lặp tiếp theo
  • node:=tạo một nút cây có giá trị trước [i]
  • nếu phần bên trái của nút trên cùng của ngăn xếp trống, thì đặt bên trái của nút trên cùng của ngăn xếp làm nút, nếu không đặt bên phải của nút trên cùng của ngăn xếp làm nút
  • chèn nút vào ngăn xếp
  • tăng tôi lên 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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)

Đầu vào

[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]

Đầu ra

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