โปรแกรมแปลง linked list เป็น zig-zag binary tree ใน Python

สมมติว่ามี singly linked list ต้องแปลงเป็น binary tree ตามกติกา: หัวเป็นราก, โหนดถัดไปเป็นลูกซ้ายถ้าค่าน้อยกว่าพาเรนต์ มิฉะนั้นเป็นลูกขวา

ตัวอย่าง: [2,1,3,4,0,5] สร้างต้นไม้ตามรูป

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน solve(node):
   • ถ้า node ว่าง: คืน None
   • root = TreeNode(node.val)
   • ถ้า node.next ไม่ว่าง:
     • ถ้า node.next.val < node.val: root.left = solve(node.next)
     • มิฉะนั้น: root.right = solve(node.next)
   • คืน root

ตัวอย่างโค้ด

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,