Giao dịch thứ tự cấp độ Zigzag cây nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm trình duyệt cấp Zigzag. Vì vậy, đối với hàng đầu tiên, hãy quét từ trái sang phải, sau đó từ phải sang trái từ hàng thứ hai, sau đó lại từ trái sang phải, v.v. Vì vậy, nếu cây giống như -

Trình tự truyền tải sẽ là [[3], [20,9], [15,7]]

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

• nếu cây trống, trả về danh sách trống

• queue:=tạo một hàng đợi và chèn root vào hàng đợi, tạo hai danh sách trống res và res2, và đặt cờ là True

• trong khi hàng đợi không trống

  • tạo danh sách các nút có trong hàng đợi, sau đó chèn vào res

  • tạo danh sách các giá trị nút có trong hàng đợi, sau đó chèn vào res2

  • nếu cờ được đặt, thì

    • i:=độ dài của danh sách con cuối cùng trong res - 1

    • trong khi tôi> =0

      • nếu phần tử thứ i của danh sách con cuối cùng trong res có cây con bên phải, thì

        • chèn cây con bên phải vào hàng đợi

      • nếu phần tử thứ i của danh sách con cuối cùng trong res còn lại cây con, thì

        • chèn cây con bên trái vào hàng đợi

      • giảm tôi đi 1

  • nếu không thì

    • i:=độ dài của danh sách con cuối cùng trong res - 1

    • trong khi tôi> =0

      • nếu phần tử thứ i của danh sách con cuối cùng trong res có cây con bên phải, thì

        • chèn cây con bên phải vào hàng đợi

      • nếu phần tử thứ i của danh sách con cuối cùng trong res còn lại cây con, thì

        • chèn cây con bên trái vào hàng đợi

      • giảm tôi đi 1

• trả về res2

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 insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def zigzagLevelOrder(self, root):
      if not root:
         return []
      queue = [root]
      res = []
      res2=[]
      flag = True
      while len(queue)!=0:
         res.append([i for i in queue])
         res2.append([i.data for i in queue if i.data != 0])
         queue = []
         if flag:
            i=len(res[-1])-1
         while i>=0:
            if res[-1][i].right:
               queue.append(res[-1][i].right)
            if res[-1][i].left:
               queue.append(res[-1][i].left)
            i-=1
         else:
            i=len(res[-1])-1
            while i>=0:
               if res[-1][i].left:
                  queue.append(res[-1][i].left)
               if res[-1][i].right:
                  queue.append(res[-1][i].right)
               i-=1
            flag = not flag
         return res2
ob = Solution()
tree = make_tree([3,9,20,None,None,15,7])
print(ob.zigzagLevelOrder(tree))

Đầu vào

[3,9,20,null,null,15,7]

Đầu ra

[[3], [20, 9], [15, 7]]