Tại sao BFS trên cây cần tách từng tầng rõ ràng trong phỏng vấn?
Khi học thuật toán tìm kiếm theo chiều rộng (Breadth-First Search — BFS) trên đồ thị tổng quát, ta thường chỉ viết một vòng lặp đơn while (!q.empty()): lấy đỉnh ở đầu hàng đợi ra, rồi đẩy các đỉnh kề vào cuối hàng đợi. Cách viết đó đủ để thăm mọi nút theo thứ tự khoảng cách không giảm, nhưng lại trộn lẫn ranh giới giữa tầng hiện tại và tầng kế tiếp ngay bên trong hàng đợi.
Trong phỏng vấn cấu trúc dữ liệu cây nhị phân, hầu hết đề bài không chỉ yêu cầu in ra một danh sách phẳng mà đòi hỏi tính toán theo từng tầng độ sâu (level-by-level):
- Binary Tree Level Order Traversal: Trả về mảng hai chiều
vector<vector<int>>, trong đó mỗi hàng là các nút thuộc cùng một tầng từ trái sang phải. - Binary Tree Right Side View: Trả về danh sách các nút nhìn thấy được nếu bạn đứng bên phải cây và nhìn sang (chính là nút cuối cùng của mỗi tầng!).
- Average of Levels / Maximum Level Sum: Tính trung bình cộng hoặc tìm tầng có tổng giá trị các nút lớn nhất.
- Binary Tree Zigzag Level Order Traversal: Tầng chẵn đọc từ trái sang phải, tầng lẻ đọc từ phải sang trái.
- Minimum Depth of Binary Tree: Tìm khoảng cách ngắn nhất từ gốc tới một nút lá bất kỳ (dừng ngay ở tầng đầu tiên bắt gặp nút không có con).
Trước khi bắt đầu viết code, bạn hãy hỏi người phỏng vấn 3 câu hỏi ngắn để làm rõ hợp đồng dữ liệu:
- Cây rỗng (
root == null) trả về gì? Thông thường trả về danh sách rỗng[](số tầng bằng0), không phải[[]]. - Giá trị các nút có thể âm hoặc vượt phạm vi 32-bit khi cộng tổng tầng không? Ở bài Maximum Level Sum hoặc Average of Levels, tổng một tầng hoàn toàn có thể tràn
intnếu các nút mang giá trị cỡ10^9, nên biến cộng dồn trên từng tầng cần dùnglong long(longtrong Java). - Cây có thể suy biến thành đường thẳng (skewed tree) sâu tới bao nhiêu nút? Nếu cây lệch hoàn toàn với \(n = 10^5\) nút, đệ quy DFS có thể gây tràn ngăn xếp (Stack Overflow), trong khi BFS dùng hàng đợi trên bộ nhớ Heap lại hoàn toàn an toàn.
Chìa khóa của mẫu BFS theo tầng nằm ở đúng một dòng lệnh ngay đầu thân vòng lặp while (!q.empty()): chụp lại số lượng nút đang có trong hàng đợi int sz = q.size(); rồi chạy vòng lặp for (int i = 0; i < sz; i++) (dừng khi i >= sz). Vì mọi nút con sinh ra trong vòng for này đều được đẩy vào cuối hàng đợi, đúng sz nút lấy ra ở đầu hàng đợi chính là toàn bộ các nút của tầng hiện tại.
Bất biến hàng đợi hai lớp và cách trích xuất góc nhìn bên phải (Right Side View)
Tại sao chỉ một phép gán int sz = q.size(); lại phân tách được các tầng mà không cần lưu kèm cặp (node, depth) trong hàng đợi? Hãy xét bất biến quy nạp theo độ sâu \(d\):
- Cơ sở (\(d = 0\)): Trước khi vào vòng lặp
while, ta chỉ đẩy duy nhất nút gốcrootvào hàng đợiq. Như vậy tại đầu vòng lặp thứ nhất,qchứa toàn bộ tầng \(0\) (sz = 1). - Bước quy nạp: Giả sử đầu vòng lặp thứ \(d\), hàng đợi
qchứa đúng toàn bộ các nút của tầng \(d\) theo thứ tự từ trái sang phải (gồmsznút). Trong vòng lặpforchạy đúngszlần:- Ta lần lượt lấy hết
sznút của tầng \(d\) ra khỏi đầu hàng đợi. - Với mỗi nút lấy ra, ta đẩy con trái (
left) rồi con phải (right) (nếu khácnull) vào cuối hàng đợi. - Ngay khi vòng
forkết thúc, toàn bộsznút của tầng \(d\) đã rời khỏiq, và những gì còn lại trongqchính là toàn bộ các nút của tầng \(d + 1\) cũng theo đúng thứ tự từ trái sang phải!
- Ta lần lượt lấy hết
Nhờ bất biến này, bài toán Binary Tree Right Side View trở thành một hệ quả miễn phí: trong sz nút của tầng \(d\), nút lấy ra ở lượt thứ i == sz - 1 (tức phần tử cuối cùng row.back() của tầng đó) chính là nút nằm ngoài cùng bên phải ở độ sâu \(d\). Tương tự, nút ở lượt i == 0 là góc nhìn từ bên trái (Left Side View).
Chạy tay từng bước trên cây [3, 9, 20, null, null, 15, 7]
Xét cây nhị phân cho dưới dạng mảng theo mức: gốc là 3 (chỉ số 0), con trái của 3 là 9 (chỉ số 1), con phải của 3 là 20 (chỉ số 2); nút 9 không có con (null, null ở chỉ số 3, 4); nút 20 có con trái 15 (chỉ số 5) và con phải 7 (chỉ số 6).
Tầng d |
Hàng đợi q đầu tầng |
Giá trị sz = q.size() |
Diễn biến trong vòng lặp for (i = 0 .. sz - 1) |
Mảng tầng row thu được |
Nút phải cùng (Right View) |
|---|---|---|---|---|---|
0 |
[3] |
1 |
i = 0: lấy 3, đẩy con trái 9 và con phải 20 vào q |
[3] |
3 |
1 |
[9, 20] |
2 |
i = 0: lấy 9 (không có con); i = 1: lấy 20, đẩy con trái 15 và con phải 7 vào q |
[9, 20] |
20 |
2 |
[15, 7] |
2 |
i = 0: lấy 15 (lá); i = 1: lấy 7 (lá) |
[15, 7] |
7 |
| Kết thúc | [] (rỗng) |
0 |
Thoát vòng lặp while |
Tổng cộng 3 tầng |
[3, 20, 7] |
Code mẫu C++17, Python và Java 21
Chương trình dưới đây đọc cây nhị phân dạng mảng đánh chỉ số kiểu heap (nút ở chỉ số u có con trái ở 2u + 1, con phải ở 2u + 2, ô trống ghi "null"; khác chuỗi của LeetCode, vốn bỏ qua con của nút null), thực hiện duyệt BFS theo từng tầng để in ra tổng số tầng, danh sách các nút trên từng tầng, và dòng cuối cùng in ra danh sách các nút nhìn từ bên phải (Right Side View).
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n) || n == 0) {
cout << "0\n";
return 0;
}
vector<string> vals(n);
for (int i = 0; i < n; i++) cin >> vals[i];
if (vals[0] == "null") {
cout << "0\n";
return 0;
}
queue<int> q;
q.push(0);
vector<vector<string>> levels;
vector<string> right_view;
while (!q.empty()) {
int sz = (int)q.size();
vector<string> row;
for (int i = 0; i < sz; i++) {
int u = q.front();
q.pop();
row.push_back(vals[u]);
int left = 2 * u + 1, right = 2 * u + 2;
if (left < n && vals[left] != "null") q.push(left);
if (right < n && vals[right] != "null") q.push(right);
}
right_view.push_back(row.back());
levels.push_back(row);
}
cout << levels.size() << '\n';
for (const auto& row : levels) {
for (size_t i = 0; i < row.size(); i++) {
cout << (i ? " " : "") << row[i];
}
cout << '\n';
}
for (size_t i = 0; i < right_view.size(); i++) {
cout << (i ? " " : "") << right_view[i];
}
cout << '\n';
return 0;
}
import collections
import sys
def main() -> None:
tokens = sys.stdin.read().split()
if not tokens:
print(0)
return
n = int(tokens[0])
if n == 0:
print(0)
return
vals = tokens[1 : 1 + n]
if vals[0] == "null":
print(0)
return
q = collections.deque([0])
levels: list[list[str]] = []
right_view: list[str] = []
while q:
sz = len(q)
row: list[str] = []
for _ in range(sz):
u = q.popleft()
row.append(vals[u])
left, right = 2 * u + 1, 2 * u + 2
if left < n and vals[left] != "null":
q.append(left)
if right < n and vals[right] != "null":
q.append(right)
right_view.append(row[-1])
levels.append(row)
print(len(levels))
for row in levels:
print(" ".join(row))
print(" ".join(right_view))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
System.out.println(0);
return;
}
int n = sc.nextInt();
if (n == 0) {
System.out.println(0);
return;
}
String[] vals = new String[n];
for (int i = 0; i < n; i++) vals[i] = sc.next();
if (vals[0].equals("null")) {
System.out.println(0);
return;
}
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(0);
List<List<String>> levels = new ArrayList<>();
List<String> rightView = new ArrayList<>();
while (!q.isEmpty()) {
int sz = q.size();
List<String> row = new ArrayList<>();
for (int i = 0; i < sz; i++) {
int u = q.remove();
row.add(vals[u]);
int left = 2 * u + 1, right = 2 * u + 2;
if (left < n && !vals[left].equals("null")) q.add(left);
if (right < n && !vals[right].equals("null")) q.add(right);
}
rightView.add(row.get(row.size() - 1));
levels.add(row);
}
System.out.println(levels.size());
for (List<String> row : levels) {
System.out.println(String.join(" ", row));
}
System.out.println(String.join(" ", rightView));
}
}
Độ phức tạp thời gian, bộ nhớ và so sánh với DFS
- Thời gian:
O(n)vớinlà số nút của cây. Mỗi nút được đẩy vào hàng đợi đúng 1 lần và lấy ra khỏi hàng đợi đúng 1 lần; mỗi thao tácpush/poptốnO(1). - Bộ nhớ phụ:
O(W)vớiWlà bề rộng lớn nhất của một tầng trên cây (không tính bộ nhớ lưu mảng kết quả trả về).- Trong trường hợp cây nhị phân đầy đủ cân bằng (full balanced binary tree), tầng lá cuối cùng có tới \(\lceil n / 2 \rceil\) nút, nên hàng đợi
qtại thời điểm đỉnh điểm chứaO(n)nút. - So với DFS đệ quy (tốn
O(H)bộ nhớ ngăn xếp vớiHlà chiều cao cây): nếu cây rất sâu và hẹp (cây suy biến \(H = n, W = 1\)) thì BFS tiết kiệm bộ nhớ hơn (O(1)so vớiO(n)); ngược lại nếu cây thấp và tán rất rộng (\(H = \log n, W = n/2\)) thì DFS dùng ít bộ nhớ phụ hơn (O(log n)so vớiO(n)). Nêu được sự đánh đổi giữaO(W)của BFS vàO(H)của DFS là điểm cộng rất lớn trong vòng phỏng vấn!
- Trong trường hợp cây nhị phân đầy đủ cân bằng (full balanced binary tree), tầng lá cuối cùng có tới \(\lceil n / 2 \rceil\) nút, nên hàng đợi
Mở rộng sang các bài toán cùng khuôn và Đường đi lớn nhất trên cây
Từ khung sz = q.size(), bạn chỉ cần thay đổi vài dòng xử lý trong từng tầng để giải quyết cả họ bài toán cây nhị phân:
| Bài toán phỏng vấn | Điều chỉnh trên khung BFS theo tầng | Ghi chú quan trọng |
|---|---|---|
| Binary Tree Zigzag Level Order | Dùng một biến cờ left_to_right đảo chiều sau mỗi tầng; hoặc điền vào row tại chỉ số left_to_right ? i : (sz - 1 - i) |
Tránh gọi reverse(row) nếu muốn ghi thẳng vào vị trí đích trong O(1) mỗi nút |
| Populating Next Right Pointers | Trong vòng for, nếu i + 1 < sz thì gán u->next = q.front() |
Giải pháp dùng hàng đợi tốn O(W) bộ nhớ; có thể tối ưu xuống O(1) bằng cách dùng chính con trỏ next của tầng trên để duyệt tầng dưới |
| Maximum Width of Binary Tree | Lưu cặp (node, index) với con trái là 2 * idx, con phải là 2 * idx + 1; độ rộng tầng là last_idx - first_idx + 1 |
Phải chuẩn hóa idx = idx - first_idx ở đầu mỗi tầng để 2 * idx không tràn số nguyên 64-bit trên cây sâu 3000 tầng |
| Binary Tree Maximum Path Sum | Bài toán này cần thông tin từ con truyền ngược lên cha (hậu thứ tự Post-order DFS), không dùng BFS từ trên xuống | Tại mỗi nút u, cập nhật đường đi vắt qua u là u->val + left_gain + right_gain, nhưng chỉ trả lên cha nhánh đơn lớn nhất u->val + max(left_gain, right_gain) |
Sự đối lập ở dòng cuối bảng trên rất quan trọng khi nhận diện dạng bài trong phòng thi:
- Khi thông tin đi từ gốc xuống lá hoặc ngang hàng theo độ sâu (tầng thứ \(d\), khoảng cách ngắn nhất, nút bên phải mỗi tầng) → chọn BFS theo tầng.
- Khi giá trị của nút cha phụ thuộc vào kết quả tổng hợp từ cây con trái và cây con phải (như chiều cao cây, đường kính cây, hay Đường đi có tổng lớn nhất — Binary Tree Maximum Path Sum) → chọn DFS hậu thứ tự (Post-order) với
left_gain = max(0, dfs(u->left)).
Các lỗi sai hay gặp và cách tự kiểm tra code
- Viết
for (int i = 0; i < q.size(); i++)trực tiếp trong điều kiện vòng lặpfor: Đây là lỗi tai hại nhất! Vì bên trong thân vòngforbạn liên tục gọiq.push(...)để thêm các nút con của tầng sau (q.size() > sz), giá trịq.size()sẽ tăng lên ở mỗi bước lặp và vòngforsẽ nuốt luôn cả các tầng kế tiếp vào chung một hàng. Bạn bắt buộc phải tách biến tĩnhint sz = q.size();trước khi vào vòngfor. - Dùng
list.pop(0)thay vìcollections.deque.popleft()trong Python: Lấy phần tử đầu củalisttrong Python phải dịch chuyển toàn bộ các phần tử còn lại sang trái một ô, làm mỗi lệnhpop(0)tốnO(n)và đẩy tổng thời gian BFS lênO(n²). Hãy luôn dùngcollections.deque. - Đẩy cả nút
nullvào hàng đợi mà quên lọc trước: Nếu bạn đẩyu->leftvàu->rightbất chấp chúng bằngnull, biếnszở tầng sau sẽ đếm cả các con trỏ rỗng và làm sai lệch phần tử cuối tầngrow.back()trong bài Right Side View. Hãy luôn kiểm traif (u->left != nullptr) q.push(u->left);trước khi đẩy vào hàng đợi.
Để tự kiểm tra code trước khi nộp, bạn hãy chạy thử trên 3 cây biên:
- Cây rỗng (
n = 0hoặc gốc lànull→ in ra0tầng). - Cây chỉ có đúng 1 nút gốc (
[1]→1tầng[1], Right View là[1]). - Cây lệch trái ở tầng sâu hơn tầng phải:
[1, 2, 3, 4, null](Tầng 0 là[1], Tầng 1 là[2, 3], Tầng 2 chỉ có nút4nằm ở nhánh trái nên nhìn từ bên phải ở tầng 2 sẽ thấy nút4→ Right View là[1, 3, 4], giúp bắt ngay lỗi của những ai chỉ đi một mạch theo con trỏroot->right).
Luyện ngay trên Big-O Coding
Hãy thực hành ngay kỹ thuật duyệt cây theo tầng, góc nhìn bên phải và đường đi trên cây nhị phân với 3 bài tập chọn lọc trong lộ trình Coding Interview 150 dưới đây.
Câu hỏi thường gặp
Bài Binary Tree Right Side View có thể giải bằng DFS thay vì BFS được không?
Hoàn toàn được. Nếu dùng DFS truyền theo tham số độ sâu depth, bạn chỉ cần ưu tiên gọi đệ quy sang nhánh con phải trước rồi mới sang nhánh con trái (dfs(u->right, depth + 1) trước dfs(u->left, depth + 1)). Khi đó, nút đầu tiên bạn chạm tới ở mỗi độ sâu depth (kiểm tra bằng điều kiện if (depth == right_view.size())) chắc chắn là nút nằm ngoài cùng bên phải của tầng đó.
Làm sao để trả về danh sách các tầng từ dưới đáy lên gốc (Bottom-Up Level Order Traversal)?
Bạn không cần thay đổi bất kỳ dòng nào trong thuật toán BFS từ trên xuống. Hãy cứ thu thập danh sách các tầng levels từ gốc xuống đáy như bình thường, rồi ở bước cuối cùng trước khi trả về, gọi lệnh đảo ngược mảng ngoài cùng std::reverse(levels.begin(), levels.end()) (hoặc levels[::-1] trong Python, Collections.reverse(levels) trong Java). Thao tác đảo ngược mảng các con trỏ hàng chỉ tốn O(H) thời gian.
Tại sao trong Java nên dùng ArrayDeque thay vì LinkedList để làm hàng đợi BFS?
Trong Java 21, cả ArrayDeque và LinkedList đều cài đặt giao diện Queue. Tuy nhiên, ArrayDeque lưu trữ dữ liệu trên một mảng vòng liên tiếp trong bộ nhớ đệm (cache-friendly) và không tốn chi phí cấp phát một đối tượng Node mới trên Heap cho mỗi lần add/remove như LinkedList, nên chạy nhanh hơn và nhẹ bộ nhớ hơn đáng kể trong các bài duyệt cây lớn. Chỉ lưu ý rằng ArrayDeque không cho phép chèn phần tử null.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


