LeetCode Q297: Serialize and Deserialize Binary Tree (hard)

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.

Solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Codec {
	public:
	string serialize(TreeNode* root) {
	string res;
	queue<TreeNode*> myQ;
	if(root==NULL)
	return res;
	myQ.push(root);
	while(!myQ.empty()){
	TreeNode* node = myQ.front();
	myQ.pop();
	if(node==NULL){
	res = res + string(" ") + string("#");
	continue;
	}
	myQ.push(node->left);
	myQ.push(node->right);
	res = res.length()==0? to_string(node->val) : res + string(" ") + to_string(node->val);
	}
	return res;
	}
	void split(const std::string &s, char delim, std::vector<std::string> &elems) {
	std::stringstream ss(s);
	std::string item;
	while (std::getline(ss, item, delim)) {
	elems.push_back(item);
	}
	}
	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
	if(data.length()==0)
	return NULL;
	vector<string> elems;
	split(data, ' ', elems);
	int p=0;
	queue<TreeNode*> myQ;
	TreeNode* root = new TreeNode(stoi(elems[p]));
	myQ.push(root);
	p++;
	while(!myQ.empty()){
	TreeNode* node = myQ.front();
	myQ.pop();
	string sl = elems[p++];
	string sr = elems[p++];
	if(sl!=string("#")){
	TreeNode* nl = new TreeNode(stoi(sl));
	node->left = nl;
	myQ.push(nl);
	}
	if(sr!=string("#")){
	TreeNode* nr = new TreeNode(stoi(sr));
	node->right = nr;
	myQ.push(nr);
	}
	}
	return root;
	}
	};
	// Your Codec object will be instantiated and called as such:
	// Codec codec;
	// codec.deserialize(codec.serialize(root));

view raw Q297.cpp hosted with ❤ by GitHub