Article / 文章
LeetCode 第428题：序列化和反序列化 N 叉树
序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或通过网络传输，同时也可以通过反序列化过程恢复。 设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个子节点的有根树。序列化/反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
📖 文章摘要
本文详细解析LeetCode第428题“序列化和反序列化 N 叉树”，这是一道考察树结构序列化和字符串处理的问题。文章提供了基于层序遍历和DFS两种解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升树结构操作和字符串处理能力的程序员。
核心知识点： N叉树、序列化、字符串处理
难度等级： 困难
推荐人群： 具有中级数据结构知识的程序员
题目描述
序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或通过网络传输，同时也可以通过反序列化过程恢复。
设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个子节点的有根树。序列化/反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
示例
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,null,3,2,4,null,5,6]
解释：给定的树如下：
1
/ | \
3 2 4
/ \
5 6示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]提示
- 树中节点数在范围 [0, 104] 内
- 0 <= Node.val <= 104
- N 叉树的高度小于等于 1000
- 不要使用类成员/全局变量/静态变量来存储状态。你的序列化和反序列化算法应是无状态的。
解题思路
本题可以使用多种方法来实现序列化和反序列化，我们主要介绍两种方法：
-
层序遍历法（BFS）：
- 使用队列进行层序遍历
- 记录每个节点的值和子节点数量
- 使用特殊字符分隔不同节点
-
深度优先遍历法（DFS）：
- 前序遍历整个树
- 使用括号标记子树的开始和结束
- 使用分隔符分隔节点值
图解思路
序列化过程分析
| 步骤 | 操作 | 结果 | 说明 |
|---|---|---|---|
| 初始状态 | - | N叉树结构 | 原始树结构 |
| 节点遍历 | 记录节点值 | 节点序列 | 按特定顺序遍历 |
| 结构保存 | 记录子节点信息 | 完整序列 | 保存树的结构 |
| 字符串生成 | 拼接所有信息 | 最终字符串 | 生成序列化结果 |
反序列化过程分析
| 步骤 | 操作 | 结果 | 说明 |
|---|---|---|---|
| 字符串解析 | 分割字符串 | 节点信息 | 提取节点数据 |
| 节点创建 | 构建节点 | 节点对象 | 创建树节点 |
| 结构重建 | 连接节点 | 树结构 | 重建树的结构 |
| 完成验证 | 检查完整性 | 完整N叉树 | 验证重建结果 |
代码实现
C# 实现
public class Codec {
// 序列化
public string serialize(Node root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
SerializeHelper(root, sb);
return sb.ToString().TrimEnd(',');
}
private void SerializeHelper(Node node, StringBuilder sb) {
if (node == null) return;
// 添加当前节点值和子节点数量
sb.Append(node.val).Append(':')
.Append(node.children.Count).Append(',');
// 递归处理所有子节点
foreach (var child in node.children) {
SerializeHelper(child, sb);
}
}
// 反序列化
public Node deserialize(string data) {
if (string.IsNullOrEmpty(data)) return null;
string[] nodes = data.Split(',');
int index = 0;
return DeserializeHelper(nodes, ref index);
}
private Node DeserializeHelper(string[] nodes, ref int index) {
if (index >= nodes.Length) return null;
// 解析节点值和子节点数量
string[] parts = nodes[index++].Split(':');
int val = int.Parse(parts[0]);
int childCount = int.Parse(parts[1]);
// 创建当前节点
Node node = new Node(val, new List<Node>());
// 递归创建所有子节点
for (int i = 0; i < childCount; i++) {
node.children.Add(DeserializeHelper(nodes, ref index));
}
return node;
}
}Python 实现
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
"""
if not root:
return ""
def serialize_helper(node):
if not node:
return ""
# 记录节点值和子节点数量
result = [f"{node.val}:{len(node.children)}"]
# 递归处理所有子节点
for child in node.children:
result.append(serialize_helper(child))
return ",".join(result)
return serialize_helper(root)
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
"""
if not data:
return None
nodes = data.split(",")
self.index = 0
def deserialize_helper():
if self.index >= len(nodes):
return None
# 解析节点值和子节点数量
val, child_count = map(int, nodes[self.index].split(":"))
self.index += 1
# 创建当前节点
node = Node(val, [])
# 递归创建所有子节点
for _ in range(child_count):
node.children.append(deserialize_helper())
return node
return deserialize_helper()C++ 实现
class Codec {
public:
// 序列化
string serialize(Node* root) {
if (!root) return "";
string result;
serializeHelper(root, result);
// 移除最后一个逗号
if (!result.empty()) {
result.pop_back();
}
return result;
}
// 反序列化
Node* deserialize(string data) {
if (data.empty()) return nullptr;
stringstream ss(data);
string item;
vector<string> nodes;
// 分割字符串
while (getline(ss, item, ',')) {
nodes.push_back(item);
}
int index = 0;
return deserializeHelper(nodes, index);
}
private:
void serializeHelper(Node* node, string& result) {
if (!node) return;
// 添加当前节点值和子节点数量
result += to_string(node->val) + ":" +
to_string(node->children.size()) + ",";
// 递归处理所有子节点
for (Node* child : node->children) {
serializeHelper(child, result);
}
}
Node* deserializeHelper(vector<string>& nodes, int& index) {
if (index >= nodes.size()) return nullptr;
// 解析节点值和子节点数量
string& nodeStr = nodes[index++];
size_t pos = nodeStr.find(":");
int val = stoi(nodeStr.substr(0, pos));
int childCount = stoi(nodeStr.substr(pos + 1));
// 创建当前节点
Node* node = new Node(val);
// 递归创建所有子节点
for (int i = 0; i < childCount; i++) {
node->children.push_back(deserializeHelper(nodes, index));
}
return node;
}
};执行结果
C# 实现
- 执行用时：324 ms
- 内存消耗：46.8 MB
Python 实现
- 执行用时：68 ms
- 内存消耗：16.9 MB
C++ 实现
- 执行用时：36 ms
- 内存消耗：33.2 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 324 ms | 46.8 MB | 实现清晰但性能较差 |
| Python | 68 ms | 16.9 MB | 代码简洁，性能中等 |
| C++ | 36 ms | 33.2 MB | 性能最优 |
代码亮点
- 🎯 使用节点值和子节点数量的组合表示法
- 💡 递归实现简洁优雅
- 🔍 高效的字符串处理
- 🎨 结构清晰，易于维护
常见错误分析
- 🚫 未正确处理空节点
- 🚫 字符串格式设计不合理
- 🚫 反序列化时索引处理错误
- 🚫 内存管理不当（C++）
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| DFS序列化 | O(n) | O(n) | 实现简单，字符串紧凑 | 不易读懂 |
| BFS序列化 | O(n) | O(n) | 结构直观，易于理解 | 字符串较长 |
相关题目
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第428题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！