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

Giả sử chúng ta phải tạo một cây tìm kiếm nhị phân khớp với đường truyền đặt hàng trước đã cho. Vì vậy, nếu trình duyệt đặt trước giống như [8,5,1,7,10,12], thì đầu ra sẽ là [8,5,10,1,7, null, 12], vì vậy cây sẽ là -

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

• root:=0 ^th nút của danh sách duyệt đặt hàng trước
• stack:=một ngăn xếp và đẩy root vào ngăn xếp
• cho mỗi phần tử i từ phần tử thứ hai của danh sách đặt hàng trước
  • i:=một nút có giá trị i
  • if value of i
  • bên trái của nút trên cùng của ngăn xếp:=i
  • chèn i vào ngăn xếp
• nếu không thì
  • while ngăn xếp không trống và giá trị phần tử trên cùng của ngăn xếp
  • cuối cùng:=đầu ngăn xếp
  • phần tử pop từ ngăn xếp
• bên phải của nút cuối cùng:=i
• chèn i vào ngăn xếp

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

Ví dụ

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

Đầu vào

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

Đầu ra

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