Đường dẫn trong cây nhị phân được gắn nhãn Zigzag bằng Python

Giả sử trong cây nhị phân vô hạn trong đó mỗi nút có hai nút con, các nút được gắn nhãn theo thứ tự hàng. Bây giờ ở các hàng được đánh số lẻ (thứ nhất, thứ ba, thứ năm, ...), việc gắn nhãn từ trái sang phải và ở các hàng được đánh số chẵn (thứ hai, thứ tư, thứ sáu, ...), việc dán nhãn là từ phải sang trái . Vậy cây sẽ như thế nào -

Vì vậy, chúng ta đã đưa ra nhãn của một nút trong cây này, chúng ta phải tìm các nhãn trong đường dẫn từ gốc của cây đến nút có nhãn đó. Vì vậy, nếu đầu vào là label =14, thì đầu ra sẽ là [1,3,4,14]

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

• Xác định hai cây mảng và res, chèn 0 và 1 vào mảng cây, đặt lẻ:=1 và hiện tại:=1 và hai:=2

• nếu label =1, thì trả về một danh sách có một phần tử duy nhất là 1.

• Tạo một vòng lặp vô hạn -

  • nếu số lẻ khác 0 thì

    • max_val:=current + hai

    • temp:=max_val

    • while temp> current

      • chèn nhiệt độ vào cây

      • nếu temp =label, thì thoát ra từ vòng lặp

      • giảm nhiệt độ xuống 1

    • nếu phần tử cuối cùng của cây là nhãn, thì thoát ra từ vòng lặp

    • hiện tại:=max_val

  • nếu không thì

    • tạm thời:=hai

    • trong khi nhiệt độ không bằng 0

      • temp:=1, tăng dòng điện lên 1, sau đó tăng dòng điện thành cây

      • nếu current =label, thì đi ra hình thành vòng lặp

    • nếu phần tử cuối cùng của cây là nhãn, thì thoát ra từ vòng lặp

  • temp:=temp * 2

  • lẻ:=false nếu số lẻ khác 0, ngược lại là đúng

• index:=chiều dài của cây - 1

• trong khi chỉ mục không phải là 0

  • chèn cây [chỉ mục] vào mảng res

  • index:=index / 2

• res:=danh sách res đã đảo ngược

• trả lại res

Ví dụ (Python)

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

class Solution(object):
   def pathInZigZagTree(self, label):
      tree = []
      res = []
      tree.append(0)
      tree.append(1)
      odd = 1
      current = 1
      two = 2
      if label == 1:
         return [1]
      while True:
         if odd:
            max_val = current + two
            temp = max_val
            while temp>current:
               tree.append(temp)
               if temp == label:
                  break
               temp-=1
            if tree[-1]== label:
               break
            current = max_val
         else:
            temp = two
            while temp:
               temp-=1
               current+=1
               tree.append(current)
            if current == label:
               break
            if tree[-1]== label:
               break
         two*=2
         odd = not odd
      index = len(tree)-1
      while index:
         res.append(tree[index])
         index//=2
      res=res[::-1]
      return res
ob = Solution()
print(ob.pathInZigZagTree(14))

Đầu vào

14

Đầu ra

[1,3,4,14]