Phỏng vấn

Tuần tự hóa và Giải tuần tự Cây nhị phân (Serialize & Deserialize Binary Tree)

Khi cần lưu trữ một cấu trúc cây nhị phân xuống tệp đĩa hoặc truyền qua mạng giữa hai máy chủ, ta không thể gửi trực tiếp các địa chỉ con trỏ bộ nhớ RAM mà phải biến đổi cây thành một chuỗi ký tự phẳng (Serialization), sau đó dựng lại đúng cấu trúc cây ban đầu từ chuỗi đó ở phía nhận (Deserialization). Bài toán Serialize and Deserialize Binary Tree (LeetCode 297) kiểm tra xem ứng viên có hiểu sâu bản chất của các phép duyệt cây hay không: tại sao bình thường cần tới hai phép duyệt (Preorder và Inorder) mới dựng lại được cây, nhưng khi ta tự thiết kế định dạng chuỗi thì chỉ cần **một phép duyệt duy nhất kèm ký hiệu nút rỗng `#`** là khôi phục được mọi cây nhị phân trong thời gian $O(n)$.

Ý chính
  • Tại sao chỉ cần 1 chuỗi Preorder có ký hiệu # là đủ?: Một chuỗi duyệt tiền thứ tự (Preorder) thông thường bị mơ hồ vì không biết khi nào một nhánh con kết thúc. Khi ghi nhận tường minh mỗi con trỏ rỗng (nullptr / None) bằng ký hiệu #, mỗi nút lá được khóa chặt bởi hai dấu #, biến chuỗi token thành một biểu thức tiền tố hoàn chỉnh không cần thêm mảng trung thứ tự (Inorder) và hoạt động đúng ngay cả khi cây có các nút trùng giá trị.
  • Định lý số lượng token \(2n + 1\): Một cây nhị phân có \(n\) nút thật sẽ có tổng cộng \(2n\) liên kết con trỏ (trái và phải). Trong đó \(n - 1\) liên kết trỏ vào các nút con thật (trừ gốc), nên luôn còn đúng \(2n - (n - 1) = n + 1\) con trỏ rỗng #. Tổng số token sinh ra luôn bằng \(n + (n + 1) = 2n + 1\).
  • Kỹ thuật con trỏ token dùng chung idx khi Deserialize: Khi gọi đệ quy build() theo đúng thứ tự Gốc \(\to\) Trái \(\to\) Phải, lời gọi đệ quy của nhánh con trái sẽ tự động đọc và tiêu thụ đúng toàn bộ các token thuộc nhánh con trái rồi dừng lại ở hai dấu # cuối nhánh, giúp lời gọi nhánh con phải ngay sau đó đọc đúng vào gốc của nhánh phải trong \(O(1)\) mỗi bước.
  • Hai chuẩn cài đặt trong phỏng vấn: Duyệt tiền thứ tự đệ quy (DFS Preorder) có mã nguồn ngắn gọn nhất, trong khi duyệt theo tầng (BFS Level-order) cho chuỗi đầu ra gần với định dạng hiển thị của LeetCode (LeetCode ghi null và bỏ các nút rỗng ở cuối).

Tại sao ký hiệu nút rỗng # thay thế được cả mảng Inorder?

Trong bài toán dựng cây nhị phân cổ điển (LeetCode 105), nếu chỉ cho trước mảng duyệt tiền thứ tự (Preorder: Gốc - Trái - Phải) là [1, 2], ta không thể biết nút 2 là con trái hay con phải của nút 1. Để xóa bỏ sự mơ hồ đó, bài toán cổ điển bắt buộc phải cung cấp thêm mảng duyệt trung thứ tự (Inorder: Trái - Gốc - Phải) và yêu cầu tất cả các nút trong cây phải có giá trị đôi một khác nhau.

Tuy nhiên, trong bài toán Tuần tự hóa và Giải tuần tự (Serialize & Deserialize), chính bạn là người thiết kế quy ước chuỗi đầu ra của hàm serialize(root)! Thay vì bỏ qua các con trỏ null khi duyệt cây, nếu ta xuất ra một ký hiệu đặc biệt (chẳng hạn #) mỗi khi chạm phải một nhánh con rỗng, sự mơ hồ biến mất hoàn toàn:

  • Cây có nút 2 là con trái của 1 sẽ được mã hóa thành: "1, 2, #, #, #".
  • Cây có nút 2 là con phải của 1 sẽ được mã hóa thành: "1, #, 2, #, #".

Hơn thế nữa, cách mã hóa kèm ký hiệu # này không hề phụ thuộc vào việc giá trị các nút có phân biệt hay không: dù toàn bộ các nút trên cây đều mang giá trị bằng 0, vị trí hình học của chúng vẫn được định vị duy nhất nhờ các dấu chặn #.

Tuần tự hóa (Serialize) và Giải tuần tự (Deserialize) Cây nhị phân Duyệt tiền thứ tự (Preorder) kèm ký hiệu '#' cho nút rỗng giúp khôi phục duy nhất cây trong O(n) Cây nhị phân gốc 1 2 3 4 5 Nút 2, 4, 5 có 2 con rỗng (#, #) Chuỗi Preorder (11 token cho 5 nút thật + 6 nút #) "1, 2, #, #, 3, 4, #, #, 5, #, #" Cơ chế con trỏ đệ quy idx khi Deserialize: 1. Đọc "1" -> Tạo gốc (1), đệ quy dựng con trái. 2. Đọc "2", kế tiếp là "#", "#" -> Hoàn tất nhánh trái (2). 3. Tự động nhảy sang "3" để dựng nhánh phải mà không cần mảng trung thứ tự (Inorder). Tổng số token = 2n + 1 -> Thời gian & Bộ nhớ O(n)
Serialize & Deserialize Cây nhị phân Cây gốc 1 (trái: 2, phải: 3(4, 5)) -> Chuỗi Preorder 1. Chuỗi mã hóa tiền thứ tự (Nút - Trái - Phải) "1, 2, #, #, 3, 4, #, #, 5, #, #" • Ký hiệu '#' đánh dấu điểm dừng nhánh con rỗng. • Cây n nút luôn sinh đúng 2n + 1 token. 2. Giải mã O(n) bằng con trỏ token idx • Gặp số: cấp phát nút mới, gọi đệ quy dựng cây con trái rồi cây con phải. • Gặp '#': trả về nullptr ngay để quay lui. Mỗi token đọc đúng 1 lần -> O(n)
Hình 1: Quá trình tuần tự hóa cây nhị phân \(5\) nút (gốc 1, con trái 2, con phải 3 có hai con 4 và 5) thành chuỗi \(11\) token tiền thứ tự "1, 2, #, #, 3, 4, #, #, 5, #, #" và cơ chế con trỏ đệ quy idx khôi phục lại cây trong thời gian \(O(n)\).

Hai phương pháp thiết kế: DFS Tiền thứ tự và BFS Theo tầng

Phương pháp 1: Duyệt tiền thứ tự đệ quy (DFS Preorder) — Khuyên dùng trong phỏng vấn

Đây là phương pháp có mã nguồn súc tích và ít khả năng viết lỗi nhất trong vòng 15–20 phút phỏng vấn:

  1. Hàm serialize(root):

    • Nếu root == null, ghi token "#" vào luồng chuỗi (kèm dấu phân cách như dấu cách hoặc dấu phẩy) rồi quay lui.
    • Nếu root != null, ghi giá trị root.val, sau đó gọi đệ quy serialize(root.left) rồi serialize(root.right).
  2. Hàm deserialize(data):

    • Tách chuỗi data theo dấu phân cách thành danh sách các token tokens[0..2n] và khởi tạo một chỉ số con trỏ dùng chung idx = 0.
    • Trong hàm đệ quy build():
      • Đọc token tại tokens[idx] và tăng idx++.
      • Nếu token vừa đọc là "#", trả về null ngay lập tức (điểm dừng đệ quy).
      • Ngược lại, chuyển token thành số nguyên, cấp phát nút mới node = new TreeNode(val), rồi gọi liên tiếp: \[\text{node.left} = \text{build}(), \qquad \text{node.right} = \text{build}()\]
      • Trả về node.

Tại sao không cần truyền phạm vi chỉ số [l, r] cho nhánh trái và nhánh phải? Nhờ tính chất đóng kín của biểu thức tiền tố có dấu #: khi build() được gọi cho node.left, nó sẽ đệ quy mở rộng và dừng lại chính xác ngay khi mọi nhánh con bên trong cây con trái đều đã gặp dấu # kết thúc. Tại thời điểm build() của node.left trả kết quả về, con trỏ idx đã tự động đứng ngay tại token đầu tiên của cây con phải!

Phương pháp 2: Duyệt theo từng tầng (BFS Level-order)

Nếu người phỏng vấn yêu cầu tuần tự hóa theo tầng (giống cách hệ thống chấm bài biểu diễn cây [1, 2, 3, #, #, 4, 5]):

  • Khi serialize: Dùng một hàng đợi BFS đẩy root vào. Khác với BFS thông thường chỉ đẩy các nút khác null, ở đây ta đẩy cả con trỏ null vào hàng đợi: khi lấy một nút ra, nếu nó là null thì ghi "#", nếu khác null thì ghi node.val và đẩy cả node.left lẫn node.right vào hàng đợi.
  • Khi deserialize: Tạo nút gốc từ tokens[0] và đẩy vào hàng đợi q, đặt con trỏ đọc token i = 1. Chừng nào q chưa rỗng, lấy nút cha parent = q.pop(), đọc tokens[i++] để gắn parent.left (nếu khác "#" thì tạo nút và đẩy vào q), rồi đọc tokens[i++] kế tiếp để gắn parent.right.
Tiêu chí so sánh DFS Tiền thứ tự (Preorder + #) BFS Theo tầng (Level-order + #) Dựng từ Preorder + Inorder (Không #)
Thời gian serialize & deserialize \(O(n)\) \(O(n)\) \(O(n)\)
Bộ nhớ phụ khi chạy \(O(n)\) (chuỗi token + ngăn xếp đệ quy \(O(h)\)) \(O(n)\) (chuỗi token + hàng đợi rộng tối đa \(O(n)\)) \(O(n)\) (cần thêm bảng băm vị trí Inorder)
Hỗ trợ cây có các nút trùng giá trị? Có Có Không (bị trùng khóa trong bảng băm)
Độ dài code trong phỏng vấn Rất ngắn (\(\approx 25\) dòng) Trung bình (\(\approx 45\) dòng) Dài và phải lưu gấp đôi dữ liệu

Ví dụ chạy tay từng bước quá trình deserialize

Xét cây nhị phân trong Hình 1: gốc 1, con trái là lá 2, con phải là nút 3 (có con trái 4 và con phải 5). Hàm serialize tạo ra mảng \(11\) token (chỉ số từ \(0\) đến \(10\)):

\[\text{tokens} = [\text{"1"},\; \text{"2"},\; \text{"\#"},\; \text{"\#"},\; \text{"3"},\; \text{"4"},\; \text{"\#"},\; \text{"\#"},\; \text{"5"},\; \text{"\#"},\; \text{"\#"}]\]

Bảng dưới đây theo dõi chính xác giá trị của con trỏ idx và ngăn xếp lời gọi đệ quy khi thực thi deserialize:

Bước (idx) Token đọc được Bối cảnh lời gọi đệ quy hiện tại Hành động thực hiện Trạng thái cây sau bước này
idx = 0 "1" Gọi build() cho gốc toàn cây Tạo Node(1), chuẩn bị gọi Node(1).left = build() Có gốc 1
idx = 1 "2" Đang tìm Node(1).left Tạo Node(2), chuẩn bị gọi Node(2).left = build() 1.left = 2
idx = 2 "#" Đang tìm Node(2).left Trả về null ngay \(\to\) chốt Node(2).left = null 2.left = null
idx = 3 "#" Đang tìm Node(2).right Trả về null ngay \(\to\) chốt Node(2).right = null. Hoàn tất Node(2), quay lui về Node(1)! 2 hoàn chỉnh (lá)
idx = 4 "3" Đang tìm Node(1).right Tạo Node(3), chuẩn bị gọi Node(3).left = build() 1.right = 3
idx = 5 "4" Đang tìm Node(3).left Tạo Node(4), chuẩn bị gọi Node(4).left = build() 3.left = 4
idx = 6, 7 "#", "#" Tìm Node(4).left và Node(4).right Cả hai trả về null. Hoàn tất Node(4), quay lui về Node(3)! 4 hoàn chỉnh (lá)
idx = 8 "5" Đang tìm Node(3).right Tạo Node(5), chuẩn bị gọi Node(5).left = build() 3.right = 5
idx = 9, 10 "#", "#" Tìm Node(5).left và Node(5).right Cả hai trả về null. Hoàn tất Node(5) \(\to\) Node(3) \(\to\) Node(1). Hoàn tất toàn bộ cây

Cài đặt bằng C++17, Python và Java 21

Chương trình dưới đây cài đặt hai phương thức serialize và deserialize theo đúng thứ tự tiền thứ tự kèm # của Phương pháp 1, nhưng thay lời gọi đệ quy bằng một ngăn xếp tự quản lý. Lý do: đề LeetCode 297 cho cây tới \(10^4\) nút, và cây lệch hẳn về một phía khiến đệ quy sâu tới \(10^4\) tầng; Python mặc định dừng ở khoảng \(1000\) tầng (RecursionError), còn Java và C++ có thể tràn ngăn xếp mặc định (StackOverflowError, chương trình bị dừng) sau vài nghìn tầng. Trong serialize, ngăn xếp đẩy con phải trước rồi mới đẩy con trái, nên con trái được lấy ra trước, đúng thứ tự Gốc \(\to\) Trái \(\to\) Phải. Trong deserialize, ngăn xếp giữ các ô con trỏ đang chờ điền; ô trên đỉnh đóng vai lời gọi build() đang chờ đọc token kế tiếp. Đọc được một số thì tạo nút, gắn vào ô đó, rồi đẩy ô con phải và ô con trái của nút mới (ô con trái nằm trên, nhận ngay token sau); đọc được # thì ô đó giữ nguyên null. Thứ tự đọc token vì thế giống hệt bảng chạy tay ở trên. Để kiểm chứng vòng khép kín, chương trình đọc chuỗi token đầu vào, gọi deserialize để dựng cây nhị phân trong bộ nhớ, sau đó gọi ngược lại serialize trên cây vừa dựng và in ra chuỗi kết quả.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left = nullptr, *right = nullptr;
    explicit TreeNode(int v) : val(v) {}
};

// Duyệt tiền thứ tự bằng ngăn xếp tự quản lý thay cho đệ quy, nên cây lệch 10^4 nút không làm tràn ngăn xếp.
vector<string> serialize(TreeNode* root) {
    vector<string> out;
    vector<TreeNode*> st = {root};
    while (!st.empty()) {
        TreeNode* u = st.back();
        st.pop_back();
        if (!u) {
            out.push_back("#");
            continue;
        }
        out.push_back(to_string(u->val));
        st.push_back(u->right);  // con phải lấy ra sau
        st.push_back(u->left);   // con trái lấy ra trước: Gốc -> Trái -> Phải
    }
    return out;
}

// slots giữ địa chỉ các con trỏ đang chờ điền; ô trên đỉnh được điền trước (đúng thứ tự gọi build() của bản đệ quy).
TreeNode* deserialize(const vector<string>& tokens) {
    TreeNode* root = nullptr;
    vector<TreeNode**> slots = {&root};
    for (const string& tok : tokens) {
        if (slots.empty()) break;
        TreeNode** slot = slots.back();
        slots.pop_back();
        if (tok == "#") continue;
        TreeNode* node = new TreeNode(stoi(tok));
        *slot = node;
        slots.push_back(&node->right);  // ô con phải: điền sau khi đọc xong cây con trái
        slots.push_back(&node->left);   // ô con trái: nhận ngay token kế tiếp
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    vector<string> tokens;
    if (!(cin >> n)) {
        tokens = {"1", "2", "#", "#", "3", "4", "#", "#", "5", "#", "#"};
    } else {
        tokens.resize(n);
        for (int i = 0; i < n; i++) cin >> tokens[i];
    }
    TreeNode* root = deserialize(tokens);
    vector<string> re_out = serialize(root);
    for (size_t i = 0; i < re_out.size(); i++) {
        if (i) cout << ",";
        cout << re_out[i];
    }
    cout << "\n";
    return 0;
}

Các lỗi sai thường gặp và cách tự kiểm chứng

  1. Không dùng dấu phân cách giữa các token số: Một số ứng viên nối trực tiếp các ký tự thành chuỗi không dấu cách như "12##34##5##" và đọc từng ký tự char một khi giải mã. Cách đó lập tức bị sai hoàn toàn ngay khi nút cây mang giá trị có nhiều chữ số (ví dụ 12 bị tách nhầm thành nút 1 và nút 2) hoặc mang số âm (ví dụ -5 có dấu trừ -). Luôn dùng dấu cách ' ' hoặc dấu phẩy ',' để tách riêng từng token.
  2. Nối chuỗi bằng toán tử s = s + token trong vòng lặp hoặc đệ quy: Trong Python hoặc Java, chuỗi (str / String) là đối tượng bất biến (immutable). Nếu viết res += str(node.val) + "," qua \(O(n)\) bước đệ quy, mỗi lần cộng chuỗi sẽ cấp phát và sao chép lại toàn bộ chuỗi cũ, đẩy độ phức tạp thời gian của serialize từ \(O(n)\) lên \(O(n^2)\)! Hãy luôn dùng std::ostringstream (hoặc std::string::append) trong C++, danh sách out.append(...) kèm " ".join(out) ở bước cuối trong Python, và StringBuilder trong Java.
  3. Truyền tham trị thay vì tham chiếu cho con trỏ idx: Khi viết bản đệ quy bằng C++, biến chỉ số int& idx truyền vào hàm đệ quy build(tokens, idx) bắt buộc phải là tham chiếu (&) (hoặc biến thành viên của lớp / thuộc tính đối tượng) để các bước tiến của idx bên trong nhánh đệ quy con trái được giữ nguyên khi chuyển sang nhánh đệ quy con phải.
  4. Cách tự kiểm chứng tại nhà: Tính chất đẹp nhất của bài toán này là tính bất biến khứ hồi (Round-trip Invariance): với mọi cây hợp lệ \(T\), bạn luôn phải có serialize(deserialize(serialize(T))) == serialize(T). Hãy tự kiểm tra trên \(4\) ca biên bắt buộc: (1) cây rỗng root = null (chuỗi "#"), (2) cây chỉ có \(1\) nút gốc âm "-1000", (3) cây suy biến lệch hẳn sang trái hoặc sang phải như danh sách liên kết (thử tới \(10^4\) nút để chắc code không tràn ngăn xếp), và (4) cây có nhiều nút mang cùng một giá trị trùng nhau.

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật tái tạo cấu trúc cây từ các phép duyệt và xử lý đệ quy trên cây nhị phân, bạn hãy thực hành ngay bộ ba bài toán dưới đây trong lộ trình Coding Interview 150:

Nếu cây đầu vào là Cây nhị phân tìm kiếm (BST — LeetCode 449), ta có thể bỏ luôn các ký hiệu # để tiết kiệm bộ nhớ không?

Có! Đây chính là điểm khác biệt cốt lõi giữa bài Serialize and Deserialize Binary Tree (LeetCode 297 — cây nhị phân tổng quát) và bài Serialize and Deserialize BST (LeetCode 449 — cây tìm kiếm nhị phân). Trên cây BST, mọi nút thuộc cây con trái của u đều nhỏ hơn u.val và mọi nút thuộc cây con phải đều lớn hơn u.val. Vì vậy, khi serialize một cây BST, ta không cần xuất bất kỳ dấu # nào (chỉ tốn đúng \(n\) token thay vì \(2n + 1\) token). Khi deserialize, ta truyền dải giới hạn (low, high) xuống hàm đệ quy build(low, high): nếu tokens[idx] nằm ngoài khoảng (low, high), điều đó chứng tỏ token này không thuộc nhánh hiện tại mà thuộc nhánh tổ tiên phía trên, ta trả về null ngay mà không cần dấu #!

Tại sao không nên dùng duyệt trung thứ tự (Inorder) kèm ký hiệu # để tuần tự hóa cây nhị phân?

Dù bạn có thêm ký hiệu # cho các nút rỗng, phép duyệt trung thứ tự (Inorder: Trái - Gốc - Phải) vẫn không thể xác định được đâu là nút gốc của toàn cây khi giải mã! Chẳng hạn, cây gồm gốc 1 có con trái 2 cho chuỗi Inorder kèm # là "#, 2, #, 1, #", và cây gồm gốc 2 có con phải 1 cũng cho ra đúng chuỗi "#, 2, #, 1, #" y hệt nhau. Để giải tuần tự được bằng một con trỏ quét một lượt, nút gốc bắt buộc phải nằm ở đầu đoạn (Preorder — duyệt từ trái sang phải) hoặc ở cuối đoạn (Postorder — khi giải mã phải duyệt ngược từ cuối mảng về đầu theo thứ tự Gốc - Phải - Trái).

Làm thế nào để mở rộng thuật toán này cho Cây \(N\)-phân (N-ary Tree — LeetCode 428)?

Trong cây \(N\)-phân, mỗi nút có thể có số lượng nút con bất kỳ từ \(0\) đến \(k\) chứ không cố định là \(2\) con trái/phải. Để tuần tự hóa cây \(N\)-phân theo tiền thứ tự, ngay sau khi ghi giá trị của nút u.val, ta ghi kèm số lượng con trực tiếp u.children.size() của nút đó (hoặc dùng một dấu đóng nhánh # sau khi đã liệt kê hết danh sách các con của u). Khi giải mã, đọc u.val và số lượng con c, ta chỉ cần chạy vòng lặp for đúng c lần gọi đệ quy u.children.push_back(build()) là khôi phục được chính xác cấu trúc cây \(N\)-phân trong \(O(n)\).

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