DSAÝ tưởng: Duyệt theo chiều rộng (BFS) bằng queue. Mẹo tách tầng: trước mỗi vòng lặp, chụp lại queue.length — đó chính là số node của tầng hiện tại, xử đúng bấy nhiêu node rồi mới sang tầng sau.
Hình dung: quét đèn pin từ gốc cây xuống, soi hết một hàng ngang rồi mới hạ xuống hàng dưới.
function levelOrder(root: TreeNode | null): number[][] {
const res: number[][] = []
if (!root) return res
const queue: TreeNode[] = [root]
while (queue.length) {
const size = queue.length // chốt số node của tầng này
const level: number[] = []
for (let i = 0; i < size; i++) {
const node = queue.shift()!
level.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
res.push(level)
}
return res
}Độ phức tạp: thời gian O(n), bộ nhớ O(n) (tầng rộng nhất có thể tới n/2 node).
Lưu ý: queue.shift() của array JS là O(n); với input lớn nên dùng con trỏ head thay cho shift để giữ O(n) tổng thể.
Idea: Breadth-first (BFS) with a queue. Level-splitting trick: before each loop, snapshot queue.length — that's the count of nodes in the current level; process exactly that many before moving on.
Picture it: sweeping a flashlight down the tree, lighting one horizontal row fully before dropping to the next.
function levelOrder(root: TreeNode | null): number[][] {
const res: number[][] = []
if (!root) return res
const queue: TreeNode[] = [root]
while (queue.length) {
const size = queue.length // lock this level's node count
const level: number[] = []
for (let i = 0; i < size; i++) {
const node = queue.shift()!
level.push(node.val)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
res.push(level)
}
return res
}Complexity: time O(n), space O(n) (the widest level can hold up to n/2 nodes).
Note: JS array shift() is O(n); for large inputs use a head pointer instead of shift to keep overall O(n).