企业官网建设流程全解析

题目描述：

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示:输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []输出：[]

示例 3：

输入：root = [1]输出：[1]

示例 4：

输入：root = [1,2]输出：[1,2]

解题思路：

方法一：前序遍历

为什么用前序遍历？

• 前序：根 → 左 → 右，顺序清晰

• 反序列化时，第一个就是根节点，方便递归构建

关键：用"null"标记空节点

如果不标记空节点，无法唯一确定树的结构。比如：

1 / 2 和 1 \ 2

前序都是[1, 2]，无法区分。加上null后：

• 第一种：1,2,null,null,null

• 第二种：1,null,2,null,null

就能唯一确定了。

具体过程示例：

1 / \ 2 3 / \ 4 5 前序序列化: "1,2,null,null,3,4,null,null,5,null,null"

代码实现：

class Codec { public: // 序列化：前序遍历 string serialize(TreeNode* root) { string result; serializeHelper(root, result); return result; } // 反序列化：前序遍历重建 TreeNode* deserialize(string data) { queue<string> q; stringstream ss(data); string token; while (getline(ss, token, ',')) { q.push(token); } return deserializeHelper(q); } private: void serializeHelper(TreeNode* node, string& result) { if (node == nullptr) { result += "null,"; return; } result += to_string(node->val) + ","; serializeHelper(node->left, result); serializeHelper(node->right, result); } TreeNode* deserializeHelper(queue<string>& q) { string token = q.front(); q.pop(); if (token == "null") { return nullptr; } TreeNode* node = new TreeNode(stoi(token)); node->left = deserializeHelper(q); node->right = deserializeHelper(q); return node; } };

复杂度分析：

设n是节点数。

关键细节：

1. 为什么用,分隔？

因为节点值可能是多位数（如123），需要分隔符区分。

2. 为什么用queue存储 token？

反序列化时需要按顺序取出 token，队列的 FIFO 特性正好符合。

3.stringstream+getline的用法

stringstream ss(data); string token; while (getline(ss, token, ',')) { q.push(token); }

按,分割字符串，逐个存入队列。

4. 为什么用前序而不是中序？

中序无法唯一确定树（需要前序+中序或后序+中序）。前序加上null标记，单独就能唯一确定树。

方法二：BFS 层序遍历

代码实现：

class Codec { public: string serialize(TreeNode* root) { if (!root) return ""; string result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node) { result += to_string(node->val) + ","; q.push(node->left); q.push(node->right); } else { result += "null,"; } } return result; } TreeNode* deserialize(string data) { if (data.empty()) return nullptr; stringstream ss(data); string token; getline(ss, token, ','); TreeNode* root = new TreeNode(stoi(token)); queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); // 处理左子节点 getline(ss, token, ','); if (token != "null") { node->left = new TreeNode(stoi(token)); q.push(node->left); } // 处理右子节点 getline(ss, token, ','); if (token != "null") { node->right = new TreeNode(stoi(token)); q.push(node->right); } } return root; } };

复杂度：时间 O(n)，空间 O(n)

两种方法对比：

前序 DFS 的优势：代码更简洁，递归思路直观。
BFS 的优势：序列化结果更紧凑。

总结：