题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 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]提示：
- 树中结点数在范围
[0, 104]内 -1000 <= Node.val <= 1000
解答
- 层序遍历序列化
解题思路：
对于序列化操作，我们使用层序遍历将二叉树转化为字符串。使用队列辅助遍历，从根节点开始，依次处理每个节点，若节点为空则用字符串”null”表示，否则将节点值转化为字符串，并将其左右子节点加入队列。最后去掉最后一个多余的分隔符”,”并返回结果字符串。
对于反序列化操作，我们使用stringstream来分割字符串，并依次处理每个节点。首先根据第一个值创建根节点，并加入队列。然后依次处理队列中的节点，每次从字符串中读取两个值，分别表示当前节点的左右子节点的值。若值为”null”，则表示该节点为空，否则创建相应的节点，并加入队列。重复上述过程直到队列为空。最后返回根节点即可。
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) {
return "null";
}
// 使用层序遍历将二叉树转化为字符串
string result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node != nullptr) {
// 非空节点，将节点值转化为字符串
result += to_string(node->val);
// 将左右子节点加入队列
q.push(node->left);
q.push(node->right);
} else {
// 空节点，用"null"表示
result += "null";
}
// 每个节点值后面加上分隔符","
result += ",";
}
// 去掉最后一个多余的分隔符","
result.pop_back();
return result;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "null") {
return nullptr;
}
// 使用stringstream分割字符串
stringstream ss(data);
string item;
queue<TreeNode*> q;
// 获取根节点值
getline(ss, item, ',');
int rootVal = stoi(item);
TreeNode* root = new TreeNode(rootVal);
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// 依次获取当前节点的左右子节点值
// 并创建相应的节点
// 左右子节点值为"null"时表示为空节点
getline(ss, item, ',');
if (item != "null") {
int leftVal = stoi(item);
TreeNode* leftNode = new TreeNode(leftVal);
node->left = leftNode;
q.push(leftNode);
}
getline(ss, item, ',');
if (item != "null") {
int rightVal = stoi(item);
TreeNode* rightNode = new TreeNode(rightVal);
node->right = rightNode;
q.push(rightNode);
}
}
return root;
}
};