Chương trình chuyển danh sách liên kết đã sắp xếp thành cây nhị phân tìm kiếm trong Python

Cho danh sách liên kết đơn đã sắp xếp kích thước n. Xây dựng cây nhị phân tìm kiếm (BST) cân bằng: lấy nút giữa (k = floor(n/2)) làm gốc, đệ quy xây cây con trái từ nửa trái, cây con phải từ nửa phải.

Ví dụ: [2,4,5,7,10,15] → cây BST cân bằng.

Giải thuật (Tìm giữa bằng con trỏ nhanh/chậm)

1. Nếu node là None: trả về None.
2. Nếu node.next là None: trả về TreeNode(node.val).
3. Dùng slow, fast để tìm nút giữa: slow nhảy 1, fast nhảy 2. prev theo sau slow.
4. Ngắt liên kết: prev.next = None.
5. Tạo gốc: root = TreeNode(slow.val).
6. Đệ quy: root.left = solve(node), root.right = solve(slow.next).
7. Trả về root.

Ví dụ minh họa

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

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

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, node):
        if not node:
            return None
        if not node.next:
            return TreeNode(node.val)
        slow = fast = node
        prev = None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        root = TreeNode(slow.val)
        root.left = self.solve(node)
        root.right = self.solve(slow.next)
        return root

ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)  # Output: 2, 4, 5, 7, 10, 15,

Đầu vào

[2,4,5,7,10,15]

Đầu ra

2, 4, 5, 7, 10, 15,