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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 10^4].
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classCodec{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){stringval;in>>val;if(val=="#")returnnullptr;TreeNode*root=newTreeNode(stoi(val));root->left=_deserialize(in);root->right=_deserialize(in);returnroot;}public:// Encodes a tree to a single string.stringserialize(TreeNode*root){ostringstreamout;_serialize(root,out);returnout.str();}// Decodes your encoded data to tree.TreeNode*deserialize(stringdata){istringstreamin(data);return_deserialize(in);}};// Your Codec object will be instantiated and called as such:// Codec ser, deser;// TreeNode* ans = deser.deserialize(ser.serialize(root));
Note: In-order Traversal cannot be serialized or deserialized.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classCodec{public:// Encodes a tree to a single string.stringserialize(TreeNode*root){if(!root)return"";ostringstreamout;queue<TreeNode*>que;que.push(root);while(!que.empty()){TreeNode*node=que.front();que.pop();if(node){out<<node->val<<" ";que.push(node->left);que.push(node->right);}else{out<<"# ";}}returnout.str();}// Decodes your encoded data to tree.TreeNode*deserialize(stringdata){if(data.empty())returnnullptr;istringstreamin(data);stringval;getline(in,val,' ');TreeNode*root=newTreeNode(stoi(val));queue<TreeNode*>que;que.push(root);while(!que.empty()){TreeNode*node=que.front();que.pop();if(!getline(in,val,' '))break;if(val!="#"){TreeNode*leftChild=newTreeNode(stoi(val));node->left=leftChild;que.push(leftChild);}if(!getline(in,val,' '))break;if(val!="#"){TreeNode*rightChild=newTreeNode(stoi(val));node->right=rightChild;que.push(rightChild);}}returnroot;}};// Your Codec object will be instantiated and called as such:// Codec ser, deser;// TreeNode* ans = deser.deserialize(ser.serialize(root));