Chương trình chuyển danh sách liên kết thành cây nhị phân zig-zag trong Python

Mô tả bài toán

Cho danh sách liên kết đơn. Chuyển đổi thành cây nhị phân theo quy tắc: nút đầu là gốc; nút tiếp theo nếu giá trị nhỏ hơn cha thì thành con trái, ngược lại thành con phải.

Ví dụ: [2,1,3,4,0,5] → cây như hình (inorder: 1,3,0,5,4,2).

Giải thuật (Đệ quy)

1. Nếu nút rỗng: trả về None.
2. Tạo nút cây root với giá trị nút danh sách.
3. Nếu có nút tiếp theo:
   • Nếu giá trị tiếp theo < giá trị hiện tại: root.left = solve(next).
   • Ngược lại: root.right = solve(next).
4. Trả về root.

Ví dụ mã Python

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

Đầu vào

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

Đầu ra

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