Pattern · Tìm kiếm theo chiều rộngTrung bình
Duyệt Cây Nhị Phân Theo Từng TầngBinary Tree Level Order Traversal
Hiểu bài
Cho gốc root của một cây nhị phân. Trả về danh sách các tầng theo thứ tự từ trên xuống dưới — mỗi tầng là một mảng giá trị các nút tại tầng đó (từ trái sang phải).
Ví dụ:
ts
// 3
// / \
// 9 20
// / \
// 15 7
root = [3, 9, 20, null, null, 15, 7]
output = [[3], [9, 20], [15, 7]]
root = [1]
output = [[1]]
root = null
output = []Kết quả là mảng 2 chiều — mỗi phần tử là một tầng (level) của cây.
Cách cơ bản
O(n) time, O(h) space — h là chiều cao câyts
// DFS với tham số depth — cách này đúng nhưng ít trực quan hơn BFS
function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = []
function dfs(node: TreeNode | null, depth: number) {
if (!node) return
if (result.length === depth) result.push([])
result[depth].push(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, 0)
return result
}Vì sao cách này chậm:
DFS có thể giải được nhưng trực giác kém hơn: phải dùng tham số depth để nhét đúng tầng.
BFS tự nhiên xử lý từng tầng vì hàng đợi (queue) duyệt theo chiều rộng.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.