- 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
idxkhi Deserialize: Khi gọi đệ quybuild()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
nullvà 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
2là con trái của1sẽ được mã hóa thành:"1, 2, #, #, #". - Cây có nút
2là con phải của1sẽ đượ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 #.
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:
-
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 đệ quyserialize(root.left)rồiserialize(root.right).
- Nếu
-
Hàm
deserialize(data):- Tách chuỗi
datatheo dấu phân cách thành danh sách các tokentokens[0..2n]và khởi tạo một chỉ số con trỏ dùng chungidx = 0. - Trong hàm đệ quy
build():- Đọc token tại
tokens[idx]và tăngidx++. - Nếu token vừa đọc là
"#", trả vềnullngay 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.
- Đọc token tại
- Tách chuỗi
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 đẩyrootvào. Khác với BFS thông thường chỉ đẩy các nút khácnull, ở đây ta đẩy cả con trỏnullvào hàng đợi: khi lấy một nút ra, nếu nó lànullthì ghi"#", nếu khácnullthì ghinode.valvà đẩy cảnode.leftlẫnnode.rightvào hàng đợi. - Khi
deserialize: Tạo nút gốc từtokens[0]và đẩy vào hàng đợiq, đặt con trỏ đọc tokeni = 1. Chừng nàoqchưa rỗng, lấy nút chaparent = q.pop(), đọctokens[i++]để gắnparent.left(nếu khác"#"thì tạo nút và đẩy vàoq), rồi đọctokens[i++]kế tiếp để gắnparent.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;
}
import sys
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left = None
self.right = None
def serialize(root: TreeNode | None) -> str:
# 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 chạm giới hạn đệ quy.
out = []
stack = [root]
while stack:
u = stack.pop()
if u is None:
out.append("#")
continue
out.append(str(u.val))
stack.append(u.right) # con phải lấy ra sau
stack.append(u.left) # con trái lấy ra trước: Gốc -> Trái -> Phải
return ",".join(out)
def deserialize(tokens: list[str]) -> TreeNode | None:
# slots: 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).
dummy = TreeNode(0) # gốc thật nằm ở dummy.left
slots = [(dummy, True)] # (nút cha, True nếu là ô con trái)
for tok in tokens:
if not slots:
break
parent, is_left = slots.pop()
if tok == "#":
continue
node = TreeNode(int(tok))
if is_left:
parent.left = node
else:
parent.right = node
slots.append((node, False)) # ô con phải: điền sau khi đọc xong cây con trái
slots.append((node, True)) # ô con trái: nhận ngay token kế tiếp
return dummy.left
def main():
raw = sys.stdin.read().split()
if not raw:
tokens = ["1", "2", "#", "#", "3", "4", "#", "#", "5", "#", "#"]
else:
n = int(raw[0])
tokens = raw[1:1 + n]
root = deserialize(tokens)
print(serialize(root))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
// Một ô con trỏ đang chờ điền: con trái (left = true) hoặc con phải của parent.
record Slot(TreeNode parent, boolean left) {}
// 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.
static List<String> serialize(TreeNode root) {
List<String> out = new ArrayList<>();
ArrayList<TreeNode> stack = new ArrayList<>(); // ArrayList chứa được null, ArrayDeque thì không
stack.add(root);
while (!stack.isEmpty()) {
TreeNode u = stack.remove(stack.size() - 1);
if (u == null) {
out.add("#");
continue;
}
out.add(String.valueOf(u.val));
stack.add(u.right); // con phải lấy ra sau
stack.add(u.left); // con trái lấy ra trước: Gốc -> Trái -> Phải
}
return out;
}
// Ô trên đỉnh ngăn xếp được điền trước (đúng thứ tự gọi build() của bản đệ quy).
static TreeNode deserialize(String[] tokens) {
TreeNode dummy = new TreeNode(0); // gốc thật nằm ở dummy.left
ArrayDeque<Slot> slots = new ArrayDeque<>();
slots.push(new Slot(dummy, true));
for (String tok : tokens) {
if (slots.isEmpty()) break;
Slot s = slots.pop();
if (tok.equals("#")) continue;
TreeNode node = new TreeNode(Integer.parseInt(tok));
if (s.left()) s.parent().left = node;
else s.parent().right = node;
slots.push(new Slot(node, false)); // ô con phải: điền sau khi đọc xong cây con trái
slots.push(new Slot(node, true)); // ô con trái: nhận ngay token kế tiếp
}
return dummy.left;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] tokens;
if (!sc.hasNextInt()) {
tokens = new String[]{"1", "2", "#", "#", "3", "4", "#", "#", "5", "#", "#"};
} else {
int n = sc.nextInt();
tokens = new String[n];
for (int i = 0; i < n; i++) tokens[i] = sc.next();
}
TreeNode root = deserialize(tokens);
System.out.println(String.join(",", serialize(root)));
}
}
Các lỗi sai thường gặp và cách tự kiểm chứng
- 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ựcharmộ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ụ12bị tách nhầm thành nút1và nút2) hoặc mang số âm (ví dụ-5có dấu trừ-). Luôn dùng dấu cách' 'hoặc dấu phẩy','để tách riêng từng token. - Nối chuỗi bằng toán tử
s = s + tokentrong 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ếtres += 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ủaserializetừ \(O(n)\) lên \(O(n^2)\)! Hãy luôn dùngstd::ostringstream(hoặcstd::string::append) trong C++, danh sáchout.append(...)kèm" ".join(out)ở bước cuối trong Python, vàStringBuildertrong Java. - 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& idxtruyền vào hàm đệ quybuild(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ủaidxbên trong nhánh đệ quy con trái được giữ nguyên khi chuyển sang nhánh đệ quy con phải. - 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ỗngroot = 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)\).
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.


