leetcode 297. Serialize and Deserialize Binary Tree

逃离我推掉我的手 2022-07-26 11:26 136阅读 0赞

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.

class Codec {
    	string my_itoa(int n)
    	{
    		if (n == 0)
    			return "0";
    		bool positive = n < 0 ? false : true;
    		n = abs(n);
    		string re;
    		while (n != 0)
    		{
    			re.insert(re.begin(), n % 10 + '0');
    			n /= 10;
    		}
    		if (!positive)
    			re.insert(re.begin(), '-');
    		return re;
    	}
    	int my_atoi(string s)
    	{
    		bool posivtive = s.front() != '-';
    		if (s.front() == '-')
    			s.erase(0, 1);
    		int re = 0;
    		while (!s.empty())
    		{
    			re = 10 * re + s[0] - '0';
    			s.erase(0, 1);
    		}
    		if (!posivtive)
    			re = -re;
    		return re;
    	}
    public:
    	// Encodes a tree to a single string.
    	string serialize(TreeNode* root) {
    		if (root == NULL)
    			return "#";
    		string s;
    		vector<TreeNode*>que;
    		que.push_back(root);
    		while (!que.empty())
    		{
    			TreeNode*n = que.back();
    			que.pop_back();
    			if (n == NULL)
    				s += "#,";
    			else
    			{
    				s += my_itoa(n->val)+',';
    				que.push_back(n->right);
    				que.push_back(n->left);
    			}
    		}
    		if (s.back() == ',')
    			s.pop_back();
    		return s;
    	}
    
    	// Decodes your encoded data to tree.
    	TreeNode* deserialize(string data) {
    		if (data == "#")
    			return NULL;
    		TreeNode*root = NULL;
    		int pos = data.find(',');
    		vector<TreeNode*>que;
    		while (!data.empty())
    		{
    			string s;
    			if (pos != string::npos)
    			{
    				s = string(data.begin(), data.begin() + pos);
    				data.erase(0, pos + 1);
    			}
    			else
    			{
    				s = data;
    				data.clear();
    			}
    			if (s == "#")
    			{
    				if (que.back()->left != NULL)
    				{
    					que.pop_back();
    					pos = data.find(',');
    					continue;
    				}
    				pos = data.find(',');
    				if (pos != string::npos)
    				{
    					s = string(data.begin(), data.begin() + pos);
    					data.erase(0, pos + 1);
    				}
    				else
    				{
    					s = data;
    					data.clear();
    				}
    				
    				if (s == "#")
    					que.pop_back();
    				else
    				{
    					int val = my_atoi(s);
    					TreeNode*n = new TreeNode(val);
    					que.back()->right = n;
    					que.pop_back();
    					que.push_back(n);
    				}
    			}
    			else
    			{
    				int val = my_atoi(s);
    				if (root == NULL)
    				{
    					root = new TreeNode(val);
    					que.push_back(root);
    				}
    				else
    				{
    					TreeNode*n = new TreeNode(val);
    					if (que.back()->left == NULL)
    					{
    						que.back()->left = n;
    						que.push_back(n);
    					}
    					else
    					{
    						que.back()->right = n;
    						que.pop_back();
    						que.push_back(n);
    					}
    				}
    			}
    			pos = data.find(',');
    		}
    		return root;
    	}
    };

[how LeetCode OJ serializes a binary tree]: https://leetcode.com/faq/#binary-tree