โปรแกรมสร้างต้นไม้ค้นหาไบนารีจากลิงค์ลิสต์ที่เรียงแล้วใน Python

สมมติว่าเรามีลิงค์ลิสต์ (Linked List) ที่เรียงลำดับแล้วขนาด n เราต้องสร้างต้นไม้ค้นหาไบนารี (Binary Search Tree) โดยการนำค่าของโหนดที่ k = floor(n/2) (ตัวกลาง) มาเป็นรูท (root) จากนั้นสร้าง subtree ซ้ายและขวาแบบ recursive จากส่วนซ้ายและขวาของโหนดกลาง

ตัวอย่างเช่น หากอินพุตคือ [2, 4, 5, 7, 10, 15] ผลลัพธ์จะเป็นต้นไม้ BST ที่สมดุล

ขั้นตอนการแก้ปัญหา (Fast/Slow Pointer หาจุดกลาง)

1. หาก node เป็น null ให้คืนค่า null
2. หาก node.next เป็น null ให้คืนค่า TreeNode ใหม่ด้วยค่า node.val
3. ใช้ slow และ fast pointer หาจุดกลาง:
   • slow = fast = node, prev = None
   • วนลูป while fast และ fast.next ไม่ใช่ null:
     • prev = slow
     • slow = slow.next
     • fast = fast.next.next
4. prev.next = None (ตัดลิงค์ลิสต์ซ้าย)
5. root = TreeNode(slow.val)
6. root.left = solve(node) (สร้าง subtree ซ้าย)
7. root.right = solve(slow.next) (สร้าง subtree ขวา)
8. คืนค่า root

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

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

อินพุต

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

เอาต์พุต

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