Chương trình chuyển duyệt cấp độ cây nhị phân thành danh sách liên kết trong Python

Cho cây nhị phân tìm kiếm, chuyển thành danh sách liên kết đơn theo thứ tự duyệt cấp độ (level-order / BFS).

Ví dụ: cây như hình → danh sách [5, 4, 10, 2, 7, 15].

Giải thuật (BFS với hàng đợi)

1. Khởi tạo head = ListNode(None) (dummy), currNode = head.
2. Hàng đợi q = [root].
3. Khi q không rỗng:
   • Lấy curr = q.pop(0).
   • Nếu không None:
     • currNode.next = ListNode(curr.val).
     • currNode = currNode.next.
     • Thêm curr.left và curr.right vào q.
4. Trả về head.next.

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

Đầu vào

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)

Đầu ra

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