เส้นทางในซิกแซกที่มีป้ายกำกับไบนารีทรีใน Python

สมมติว่าในต้นไม้ไบนารีอนันต์ที่ทุกโหนดมีลูกสองคน โหนดจะถูกติดป้ายกำกับในลำดับแถว ขณะนี้อยู่ในแถวเลขคี่ (ที่หนึ่ง สาม ห้า...) การติดฉลากจะเรียงจากซ้ายไปขวา และในแถวที่มีเลขคู่ (ที่สอง สี่ หก,...) การติดฉลากจะเป็นจากขวาไปซ้าย . ต้นไม้ก็จะเหมือน −

ดังนั้นเราได้ให้ป้ายกำกับของโหนดในทรีนี้ เราต้องหาป้ายกำกับในเส้นทางจากรากของต้นไม้ไปยังโหนดที่มีป้ายกำกับนั้น ดังนั้นหากอินพุตเป็น label =14 เอาต์พุตจะเป็น [1,3,4,14]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ทรีและ res สองรายการ แทรก 0 และ 1 ลงในทรีอาร์เรย์ ตั้งค่าคี่ :=1 และปัจจุบัน :=1 และสอง :=2

• ถ้า label =1 ให้ส่งคืนรายการที่มีองค์ประกอบเดียว 1

• สร้างหนึ่งวงไม่สิ้นสุด -

  • ถ้าคี่ไม่ใช่ศูนย์ แล้ว

    • max_val :=ปัจจุบัน + สอง

    • อุณหภูมิ :=max_val

    • ในขณะที่อุณหภูมิ> ปัจจุบัน

      • ใส่อุณหภูมิลงในต้นไม้

      • ถ้า temp =label ก็ออกมาจาก loop

      • ลดอุณหภูมิลง 1

    • ถ้าองค์ประกอบสุดท้ายของ tree คือ label ก็ให้ออกมาจาก loop

    • ปัจจุบัน :=max_val

  • อย่างอื่น

    • อุณหภูมิ :=สอง

    • ในขณะที่อุณหภูมิไม่เป็นศูนย์

      • อุณหภูมิ :=1 เพิ่มกระแส 1 แล้วเพิ่มกระแสเข้าไปในต้นไม้

      • ถ้า current =label ก็ออกมาเป็นวง

    • ถ้าองค์ประกอบสุดท้ายของ tree คือ label ก็ให้ออกมาจาก loop

  • อุณหภูมิ :=อุณหภูมิ * 2

  • คี่ :=เท็จ ถ้าคี่ไม่ใช่ศูนย์ มิฉะนั้น จริง

• ดัชนี :=ความยาวของต้นไม้ – 1

• ในขณะที่ดัชนีไม่ใช่ 0

  • แทรก tree[index] ลงในอาร์เรย์ res

  • ดัชนี :=ดัชนี / 2

• res :=กลับรายการ res

• ผลตอบแทน

ตัวอย่าง(Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

14

ผลลัพธ์

[1,3,4,14]