โปรแกรมแปลงการเดินทาง Level Order ของต้นไม้ไบนารีเป็น Linked List ใน Python

สมมติว่าเรามีต้นไม้ค้นหาไบนารี (Binary Search Tree) เราต้องแปลงมันเป็น singly linked list โดยใช้การเดินทาง level-order (BFS)

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

ขั้นตอนการแก้ปัญหา (BFS with Queue)

1. สร้าง head เป็น ListNode dummy
2. currNode = head
3. q = [root] (คิวสำหรับ BFS)
4. วนลูป while q ไม่ว่าง:
   • curr = q.pop(0) (dequeue)
   • หาก curr ไม่ใช่ null:
     • currNode.next = ListNode(curr.val)
     • currNode = currNode.next
     • q.append(curr.left)
     • q.append(curr.right)
5. คืนค่า head.next

ตัวอย่างโค้ด 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.val = data
        self.left = left
        self.right = right

def print_list(head):
    ptr = head
    print('[', end='')
    while ptr:
        print(ptr.val, end=', ')
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, root):
        head = ListNode(None)
        currNode = head
        q = [root]
        
        while q:
            curr = q.pop(0)
            if curr:
                currNode.next = ListNode(curr.val)
                currNode = currNode.next
                q.append(curr.left)
                q.append(curr.right)
        
        return head.next

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head)  # Output: [5, 4, 10, 2, 7, 15, ]

อินพุต

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

เอาต์พุต

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