Khi thực hiện duyệt cây theo chiều rộng (Breadth-First Search - BFS), tại sao việc sử dụng hàng đợi (Queue) lại là lựa chọn tối ưu và làm thế nào để xử lý bài toán in cây theo từng cấp độ (Level Order Traversal)?

Question

Accepted Answer

Sử dụng Queue là bắt buộc vì tính chất FIFO (First-In-First-Out) của nó phản ánh đúng thứ tự các nút cần xử lý theo từng tầng từ trái sang phải.
Cách thực hiện:

Khởi tạo một Queue và đưa nút gốc vào.
Trong khi Queue không rỗng:
Lấy số lượng nút hiện tại trong Queue (đây chính là số nút của tầng đó).
Duyệt qua số lượng nút này, lấy từng nút ra, in giá trị và đẩy các nút con vào Queue.

Ví dụ mã giả:
def level_order(root):
    if not root: return
    queue = [root]
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.pop(0)
            print(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
Việc hiểu rõ cơ chế này giúp lập trình viên kiểm soát tốt bộ nhớ khi duyệt các cây có độ sâu lớn.

Khi thực hiện duyệt cây theo chiều rộng (Breadth-First Search - BFS), tại sao việc sử dụng hàng đợi (Queue) lại là lựa chọn tối ưu và làm thế nào để xử lý bài toán in cây theo từng cấp độ (Level Order Traversal)?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề