二叉树的序列化与反序列化（Serialize and Deserialize Binary Tree）
力扣第 297 题。把一棵二叉树转成字符串存储，再把字符串还原成原来的树。
先想清楚一个问题：为什么需要记录空节点？
只记录非空节点的前序遍历是 1,2,3，但这棵树和另一棵树可能有相同的序列：
1 1
/ \ \
2 3 2
\
3
必须把空节点也序列化进去，才能唯一还原一棵树。
最优解法：前序遍历（DFS）⭐
序列化时前序遍历，空节点写 #，节点间用 , 分隔。反序列化时同样按前序顺序消费字符串。
cpp
class Codec {
public:
// ── 序列化 ──
string serialize(TreeNode* root) {
string res;
dfs_serialize(root, res);
return res;
}
void dfs_serialize(TreeNode* node, string& res) {
if (!node) {
res += "#,";
return;
}
res += to_string(node->val) + ",";
dfs_serialize(node->left, res);
dfs_serialize(node->right, res);
}
// ── 反序列化 ──
TreeNode* deserialize(string data) {
queue<string> q;
string token;
for (char c : data) {
if (c == ',') { q.push(token); token.clear(); }
else token += c;
}
return dfs_deserialize(q);
}
TreeNode* dfs_deserialize(queue<string>& q) {
string val = q.front(); q.pop();
if (val == "#") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = dfs_deserialize(q); // 先建左子树
node->right = dfs_deserialize(q); // 再建右子树
return node;
}
};
为什么前序遍历特别适合这道题？
前序是”根 → 左 → 右”，序列化和反序列化的顺序完全一致——反序列化时每次从队列头取一个值，就知道这是当前子树的根，递归往下建，天然对应。
树: 1
/ \
2 3
/
4
序列化: 1,2,4,#,#,#,3,#,#
反序列化过程:
取 1 → 根节点
取 2 → 左子树根
取 4 → 左子树根
取 # → 4 的左为 null
取 # → 4 的右为 null
取 # → 2 的右为 null
取 3 → 右子树根
取 # → 3 的左为 null
取 # → 3 的右为 null
还原完毕 ✓
解法二：BFS 层序遍历
cpp
string serialize(TreeNode* root) {
if (!root) return "";
string res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (!node) { res += "#,"; continue; }
res += to_string(node->val) + ",";
q.push(node->left);
q.push(node->right);
}
return res;
}
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
// 分割字符串
vector<string> tokens;
string token;
for (char c : data) {
if (c == ',') { tokens.push_back(token); token.clear(); }
else token += c;
}
int i = 1;
TreeNode* root = new TreeNode(stoi(tokens[0]));
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (tokens[i] != "#") {
node->left = new TreeNode(stoi(tokens[i]));
q.push(node->left);
}
i++;
if (tokens[i] != "#") {
node->right = new TreeNode(stoi(tokens[i]));
q.push(node->right);
}
i++;
}
return root;
}
BFS 版本更直观（就是层序打印），但代码略长，反序列化需要额外维护索引。
两种解法对比
| DFS 前序 | BFS 层序 | |
|---|---|---|
| 时间 | O(n) | O(n) |
| 空间 | O(h) 递归栈 | O(w) 队列（w为最大宽度） |
| 代码简洁度 | ★★★★★ | ★★★ |
| 面试推荐 | ✅ 首选 | 作为第二思路 |
最坏情况下（满二叉树）BFS 队列宽度 O(n/2)，DFS 栈深度 O(log n)——DFS 空间更优。
面试时最容易踩的坑
① 分隔符不能省：12 和 1,2 是不同的，节点值可能是多位数甚至负数，必须有分隔符。
② 空节点必须序列化：这是还原唯一性的保证，不能只记非空节点。
③ 反序列化用队列而非下标：队列天然支持按序消费，代码更简洁，不容易越界。
把这三点在面试里主动说出来，比直接写代码更能体现理解深度。