劍指offer 37:序列化二叉樹

可采用前序周遊序列化及反序列化二叉樹

/**
 *Copyright @ 2019 Zhang Peng. All Right Reserved.
 *Filename:
 *Author: Zhang Peng
 *Date:
 *Version:
 *Description:
**/

#include<iostream>
#include<string>
#include<stack>
using namespace std;


struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};

class Solution {
public:
	char* Serialize(TreeNode *root) {
		string result;
		if (root != nullptr)
		{
			stack<TreeNode *> s;
			s.push(root);
			while (!s.empty())
			{
				TreeNode * pnode = s.top();
				s.pop();
				if (pnode != nullptr)
				{
					int v = pnode->val;
					result.append(to_string(v));
					result.append(1, '!');
				    s.push(pnode->right);
					s.push(pnode->left);
				}
				else
                   result.append(1, '#');
			}
		}

		char * cresult = new char(result.size() + 1);
		for (int i = 0; i<(int)result.size(); i++)
			cresult[i] = result[i];
		cresult[result.size()] = '\0';
		return cresult;
	}

	void creatTree(TreeNode * & t, string str, int & index)
	{
		if (index == (int)str.size())
			return;
		else
		{
			if (str[index] != '#')
			{
				int num = 0;
				while (str[index+num] != '!')
				{
					num++;
				}
				string temp = str.substr(index, num);
				int v = stoi(temp);
				t = new TreeNode(v);
				index = index + num + 1;
				creatTree(t->left, str, index);
				creatTree(t->right, str, index);
			}
			else
			{
				t = nullptr;
				index++;
				return;
			}
		}
	}

	TreeNode* Deserialize(char *str) {
		if (str == nullptr)
			return nullptr;
		string sstr;
		while (*str != '\0')
		{
			sstr.append(1, *str);
			str++;
		}
		TreeNode * t;
		int index = 0;
		creatTree(t, sstr, index);
		return t;
	}
};

int main()
{
	Solution s;
	char * str = "1!2!4!###3!11!##5!##";
	cout << "原輸入：" << endl<< str << endl;
	TreeNode * tree=s.Deserialize(str);

	char * dstr = s.Serialize(tree);
	cout << "反序列化後再對二叉樹進行序列化:" << endl<< dstr << endl;

    system("pause");
    return 0;
}