โปรแกรมแปลงรายการที่เชื่อมโยงเป็นไบนารีทรีซิกแซกใน Python

สมมติว่าเรามีรายการที่เชื่อมโยงโดยลำพัง เราต้องแปลงเป็นเส้นทางต้นไม้ไบนารีโดยใช้กฎต่อไปนี้ -

• ส่วนหัวของรายการที่เชื่อมโยงคือรูท
• โหนดที่ตามมาแต่ละโหนดคือโหนดย่อยด้านซ้ายของพาเรนต์เมื่อค่าน้อยกว่า มิฉะนั้นจะเป็นโหนดย่อยที่ถูกต้อง

ดังนั้นหากอินพุตเป็น [2,1,3,4,0,5] ผลลัพธ์จะเป็น

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

• กำหนดฟังก์ชัน Solve() นี่จะใช้โหนด
• ถ้าโหนดเป็น null แล้ว
  • คืนค่า null
• root :=สร้าง tree node ที่มีค่าเท่ากับค่าของ node
• หากโหนดถัดไปไม่เป็นโมฆะ
  • ถ้าค่าของโหนดถัดไป <ค่าของโหนด แล้ว
    • ด้านซ้ายของรูท :=แก้ (ถัดจากโหนด)
  • มิฉะนั้น
    • ด้านขวาของรูท :=แก้ (ถัดจากโหนด)
• คืนราก

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

ตัวอย่าง

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next
def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None: print_tree(root.left)
      print(root.data, end = ', ') print_tree(root.right)
class Solution:
   def solve(self, node):
      if not node:
         return None
         root = TreeNode(node.val)
      if node.next:
         if node.next.val < node.val:
            root.left = self.solve(node.next)
         else:
            root.right = self.solve(node.next)
      return root
ob = Solution()
L = make_list([2,1,3,4,0,5])
print_tree(ob.solve(L))

อินพุต

[2,1,3,4,0,5]

ผลลัพธ์

1, 3, 0, 5, 4, 2,