[LeetCode]Serialize and Deserialize Binary Tree

可以参考Construct String From Binary Tree 和 Construct Binary Tree From String的思路，代码如下：

	/**
	* 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:
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
	if(!root)return "";
	if(!root->left && !root->right)return to_string(root->val);
	int num = root->val;
	string left = serialize(root->left);
	string right = serialize(root->right);
	if(!root->right)return to_string(num) + "(" + left + ")";
	return to_string(num) + "(" + left + ")" + "(" + right + ")";
	}
	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
	data = "(" + data + ")";
	int len = data.size();
	return s2T(data, 0, len - 1);
	}
	private:
	TreeNode* s2T(string s, int lo, int hi)
	{
	if(lo + 1 > hi - 1)return nullptr;
	TreeNode* node = nullptr;
	int num = 0, i = lo + 1;
	bool isNeg = s[i] == '-'? true: false;
	if(isNeg)++i;
	while(i < hi && isdigit(s[i]))
	num = num * 10 + (s[i++] - '0');
	node = new TreeNode(isNeg? -num: num);
	if(i == hi)return node;//leaf node
	int count = 0, j = i;
	while(j <= hi)
	{
	if(s[j] == '(')++count;
	else if(s[j] == ')') --count;
	if(!count)break;
	++j;
	}
	node->left = s2T(s, i, j);
	node->right = s2T(s, j + 1, hi - 1);
	return node;
	}
	};
	// Your Codec object will be instantiated and called as such:
	// Codec codec;
	// codec.deserialize(codec.serialize(root));

view raw Serialize and Deserialize Binary Tree_1.cpp hosted with ❤ by GitHub

另外我们也可以用题目给的思路来序列化，也就是层序遍历，代码如下：

	/**
	* 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:
	const string delimiter = ",";
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
	string s = "";
	queue<TreeNode*> q;
	q.push(root);
	while(q.size())
	{
	bool hasNode = false;
	int len = q.size();
	while(len--)
	{
	auto node = q.front();
	q.pop();
	if(node)
	{
	s += to_string(node->val);
	q.push(node->left);
	q.push(node->right);
	if(node->left || node->right)
	hasNode = true;
	}
	else s += "#";
	s += delimiter;
	}
	if(!hasNode)break;
	}
	s.pop_back();
	return s;
	}
	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
	auto strs = tokenize(data);
	TreeNode* root = strs[0] == "#"? nullptr: new TreeNode(stoi(strs[0]));
	queue<TreeNode*> q;
	q.push(root);
	int i = 1;
	while(i < strs.size())
	{
	auto node = q.front();
	q.pop();
	if(strs[i] != "#")
	{
	node->left = new TreeNode(stoi(strs[i]));
	q.push(node->left);
	}
	++i;
	if(strs[i] != "#")
	{
	node->right = new TreeNode(stoi(strs[i]));
	q.push(node->right);
	}
	++i;
	}
	return root;
	}
	private:
	vector<string> tokenize(string s)
	{
	int i = 0, pos = 0;
	s += delimiter;
	vector<string> strs;
	while((pos = s.find(delimiter, i)) != string::npos)
	{
	strs.push_back(s.substr(i, pos - i));
	i = pos + delimiter.size();
	}
	return strs;
	}
	};
	// Your Codec object will be instantiated and called as such:
	// Codec codec;
	// codec.deserialize(codec.serialize(root));

view raw Serialize and Deserialize Binary Tree_2.cpp hosted with ❤ by GitHub