Phỏng vấn

Mẫu duyệt cây BFS theo từng tầng (Level Order Traversal)

Duyệt cây theo từng tầng (Level Order Traversal) gom các nút có cùng độ sâu vào từng nhóm riêng biệt từ trên xuống dưới và từ trái sang phải. Chỉ với thao tác chốt kích thước hàng đợi sz = q.size() ở đầu mỗi vòng lặp, bạn có thể giải gọn hàng loạt bài toán phỏng vấn như nhìn cây từ bên phải, duyệt zíc-zắc hay tìm tầng có tổng lớn nhất.

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:

  1. Cây rỗng (root == null) trả về gì? Thông thường trả về danh sách rỗng [] (số tầng bằng 0), không phải [[]].
  2. 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 int nế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ùng long long (long trong Java).
  3. 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ính

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.

BFS theo từng tầng (Level Order) & Góc nhìn bên phải (Right View) Tầng 0 (sz = 1) Right View: 3 Tầng 1 (sz = 2) Right View: 20 Tầng 2 (sz = 2) Right View: 7 3 9 20 15 7 Chốt int sz = q.size() đầu mỗi vòng while · Right View lấy nút thứ i == sz - 1
Level Order BFS: [3, 9, 20, 15, 7] Chốt sz = q.size() để tách từng tầng Tầng 0 (sz = 1): [3] Nút phải cùng (Right View): 3 Tầng 1 (sz = 2): [9, 20] Nút phải cùng (Right View): 20 Tầng 2 (sz = 2): [15, 7] Nút phải cùng (Right View): 7 Right Side View = [3, 20, 7] · O(n)
Hình 1. Duyệt BFS theo từng tầng trên cây nhị phân [3, 9, 20, null, null, 15, 7]: chốt kích thước sz ở mỗi tầng giúp tách riêng 3 tầng [3], [9, 20], [15, 7] và trích xuất ngay góc nhìn bên phải (Right Side View) là [3, 20, 7].

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ốc root vào hàng đợi q. Như vậy tại đầu vòng lặp thứ nhất, q chứ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 q chứa đúng toàn bộ các nút của tầng \(d\) theo thứ tự từ trái sang phải (gồm sz nút). Trong vòng lặp for chạy đúng sz lần:
    • Ta lần lượt lấy hết sz nú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ác null) vào cuối hàng đợi.
    • Ngay khi vòng for kết thúc, toàn bộ sz nút của tầng \(d\) đã rời khỏi q, và những gì còn lại trong q chí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!

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;
}

Độ phức tạp thời gian, bộ nhớ và so sánh với DFS

  • Thời gian: O(n) với n là 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ác push/pop tốn O(1).
  • Bộ nhớ phụ: O(W) với W là 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 q tại thời điểm đỉnh điểm chứa O(n) nút.
    • So với DFS đệ quy (tốn O(H) bộ nhớ ngăn xếp với H là 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ới O(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ới O(n)). Nêu được sự đánh đổi giữa O(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!

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

  1. Viết for (int i = 0; i < q.size(); i++) trực tiếp trong điều kiện vòng lặp for: Đây là lỗi tai hại nhất! Vì bên trong thân vòng for bạn liên tục gọi q.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òng for sẽ 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ĩnh int sz = q.size(); trước khi vào vòng for.
  2. Dùng list.pop(0) thay vì collections.deque.popleft() trong Python: Lấy phần tử đầu của list trong 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ệnh pop(0) tốn O(n) và đẩy tổng thời gian BFS lên O(n²). Hãy luôn dùng collections.deque.
  3. Đẩy cả nút null vào hàng đợi mà quên lọc trước: Nếu bạn đẩy u->left và u->right bất chấp chúng bằng null, biến sz ở tầng sau sẽ đếm cả các con trỏ rỗng và làm sai lệch phần tử cuối tầng row.back() trong bài Right Side View. Hãy luôn kiểm tra if (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 = 0 hoặc gốc là null → in ra 0 tầng).
  • Cây chỉ có đúng 1 nút gốc ([1] → 1 tầ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út 4 nằm ở nhánh trái nên nhìn từ bên phải ở tầng 2 sẽ thấy nút 4 → 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.

Muốn học bài bản cùng giảng viên?

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.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483