Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
1 / \ 2 3 / \ 4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.
这道题让我们对二叉树进行序列化和去序列化的操作。序列化就是将一个数据结构或物体转化为一个位序列，可以存进一个文件或者内存缓冲器中，然后通过网络连接在相同的或者另一个电脑环境中被还原，还原的过程叫做去序列化。现在让我们来序列化和去序列化一个二叉树，并给了我们例子。这题有两种解法，分别为先序遍历的递归解法和层序遍历的非递归解法。先来看先序遍历的递归解法，非常的简单易懂，我们需要接入输入和输出字符串流istringstream和ostringstream，对于序列化，我们从根节点开始，如果节点存在，则将值存入输出字符串流，然后分别对其左右子节点递归调用序列化函数即可。对于去序列化，我们先读入第一个字符，以此生成一个根节点，然后再对根节点的左右子节点递归调用去序列化函数即可，参见代码如下：
// Recursion class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; serialize(root, out); return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream in(data); return deserialize(in); } private: void serialize(TreeNode *root, ostringstream &out) { if (root) { out << root->val << ' '; serialize(root->left, out); serialize(root->right, out); } else { out << "# "; } } TreeNode* deserialize(istringstream &in) { string val; in >> val; if (val == "#") return nullptr; TreeNode *root = new TreeNode(stoi(val)); root->left = deserialize(in); root->right = deserialize(in); return root; } };
另一种方法是层序遍历的非递归解法，这种方法略微复杂一些，我们需要借助queue来做，本质是BFS算法，也不是很难理解，就是BFS算法的常规套路稍作修改即可，参见代码如下：
// Non-recursion class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; queue<TreeNode*> q; if (root) q.push(root); while (!q.empty()) { TreeNode *t = q.front(); q.pop(); if (t) { out << t->val << ' '; q.push(t->left); q.push(t->right); } else { out << "# "; } } return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if (data.empty()) return nullptr; istringstream in(data); queue<TreeNode*> q; string val; in >> val; TreeNode *res = new TreeNode(stoi(val)), *cur = res; q.push(cur); while (!q.empty()) { TreeNode *t = q.front(); q.pop(); if (!(in >> val)) break; if (val != "#") { cur = new TreeNode(stoi(val)); q.push(cur); t->left = cur; } if (!(in >> val)) break; if (val != "#") { cur = new TreeNode(stoi(val)); q.push(cur); t->right = cur; } } return res; } };
本文转自博客园Grandyang的博客，原文链接：二叉树的序列化和去序列化[LeetCode] Serialize and Deserialize Binary Tree ，如需转载请自行联系原博主。
