Binary Tree Level Order Traversal

Bài toán

Cho root của cây nhị phân. Trả về danh sách các giá trị node theo thứ tự tầng (Level-by-level). Output dạng mảng 2 chiều: [[Tầng 0], [Tầng 1], [Tầng 2]...].

Ví dụ:

Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Phân Tích & Tiếp Cận

Breadth-First Search (BFS)

Để duyệt theo tầng, ta bắt buộc dùng Queue (Hàng đợi - FIFO).

1. Bỏ root vào Queue.
2. Khi Queue chưa rỗng:
   • Xác định levelSize = số lượng node hiện có trong queue (đây là tất cả node của tầng hiện tại).
   • Duyệt đúng levelSize lần:
     • Pop node ra khỏi Queue.
     • Thêm giá trị vào mảng con currentLevel.
     • Nếu có con Left/Right -> Push vào Queue (đây sẽ là các node của tầng sau).
   • Thêm mảng currentLevel vào kết quả res.

function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];

    const res: number[][] = [];
    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        res.push(currentLevel);
    }

    return res;
}

• Time Complexity: $O(n)$ - Mỗi node vào/ra queue 1 lần.
• Space Complexity: $O(n/2) = O(n)$ - Kích thước queue lớn nhất là ở tầng lá (chiếm khoảng n/2 node).

Pattern Nhận Diện

• Mọi bài toán yêu cầu xử lý theo tầng (Level), hoặc tìm đường đi ngắn nhất (Shortest Path) trong Graph không trọng số -> BFS (Queue).