Làm thế nào để triển khai thuật toán duyệt cây theo chiều rộng (Level Order Traversal) trong Cây nhị phân và ứng dụng của nó?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Duyệt cây theo chiều rộng (Level Order Traversal hoặc Breadth-First Search) là phương pháp duyệt qua các nút của cây theo từng tầng một, từ trái sang phải, bắt đầu từ nút gốc. Để thực hiện điều này, cấu trúc dữ liệu hàng đợi (Queue) là bắt buộc nhằm duy trì thứ tự xử lý các nút.
Ví dụ mã nguồn minh họa
from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])

while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)

return result
Lưu ý kinh nghiệm thực chiến

Ứng dụng thực tế: Level Order Traversal thường được áp dụng trong việc tìm đường đi ngắn nhất, xây dựng giao diện hiển thị cây thư mục theo từng cấp độ, hoặc tuần tự hóa cây (Serialization) để lưu trữ vào cơ sở dữ liệu.
Tối ưu hóa: Sử dụng collections.deque trong Python thay vì danh sách thông thường (list) giúp thao tác lấy phần tử ở đầu hàng đợi (popleft()) đạt hiệu suất O(1) thay vì O(N).

Làm thế nào để triển khai thuật toán duyệt cây theo chiều rộng (Level Order Traversal) trong Cây nhị phân và ứng dụng của nó?

Bản chất cơ chế hoạt động

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 binary tree liên quan cùng chủ đề