Bài toán
Link đến bài toán: 515. Find Largest Value in Each Tree Row
Phân tích
Bài này khá dễ, ta dùng BFS hay DFS đều được.
Giải thuật
BFS
- Khởi tạo một queue rỗng, một mảng rỗng
result
để lưu kết quả. - Thêm node gốc vào queue.
- Khởi tạo
level = 0
- Lặp chừng nào queue không rỗng:
- Đặt
levelCount
là độ dài của queue (cũng là số node ở level hiện tại). - Với từng node trong
levelCount
node:- Lấy node ra khỏi queue.
- Set lại
result[level] = max(result[max], node.Val)
- Nếu node có con trái, thêm con trái vào queue.
- Nếu node có con phải, thêm con phải vào queue.
- Tăng
level
lên 1.
- Đặt
- Trả về
result
.
DFS
- Khởi tạo một mảng rỗng
result
để lưu kết quả. - Tạo một stack rỗng, chứa pair
(node, level)
. - Thêm node gốc vào stack.
- Lặp chừng nào stack không rỗng:
- Lấy node và level ra khỏi stack.
- Nếu
result[level]
chưa được set, setresult[level] = node.Val
. - Nếu
result[level]
đã được set, setresult[level] = max(result[level], node.Val)
. - Nếu node có con phải, thêm con phải vào stack với level tăng lên 1.
- Nếu node có con trái, thêm con trái vào stack với level tăng lên 1.
- Trả về
result
.
Cài đặt khá đơn giản, tác giả lười nên mọi người tự code nhé.