剑指offer（C++）——序列化二叉树

柔情只为你懂 2022-06-17 06:17 179阅读 0赞

##  ##

## 题目描述 ##

请实现两个函数，分别用来序列化和反序列化二叉树

解释：序列化的意思是指将一些特定的数据结构，变成有格式信息的字符串。例如对一个链表，可以将1->2->3->4->NULL序列化为"1,2,3,4"。对于序列化算法，必须支持反序列化，即在约定的格式下，可以将满足格式要求的字符串重新构造为原始的结构形式。

二叉树序列化

![Center][]![Image 1][]![Image 1][]

我们以前序遍历的顺序进行序列化，对于空结点我们用一个特殊的符号‘$’来代替，则序列化后的字符串为“1,2,4,$,$,5,$,$,3,6,$,$,7,$,$”

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) {
    		if (root == NULL)
    			return NULL;
    		string str;
    		serialize(root, str);
    		char* buffer = new char[str.size() + 1];                
    		strcpy(buffer, str.c_str());                     //将string类型的字符串转换成C_style类型并复制到一个char类型数组
    		return buffer;
    	}
    
    	void serialize(TreeNode* root, string& str)
    	{
    		if (root == NULL)
    		{
    			str += "$,";                      //叶子结点的左右子结点为空则用 $ 来代替
    			return;
    		}
    		str += to_string(root->val);             //将结点值（int）转换成字符串（string）类型
    		str += ',';
    		serialize(root->left, str);             //递归序列化结点的左子树
    		serialize(root->right, str);            //递归序列化结点的右子树
    	}
    
    	/*========================二叉树反序列化============================*/
    	TreeNode* Deserialize(char *str) {
    		if (str == NULL)
    			return NULL;
    		return deserialize(&str);
    	}
    
    	TreeNode* deserialize(char** str)
    	{
    		if (**str == '$')
    		{
    			(*str) += 2;
    			return NULL;
    		}
    		int val = 0;
    		while (**str != ','&&**str != '\0')                //把字符串类型的数字转换成int类型的数字
    		{
    			val = val * 10 + (**str - '0');
    			++(*str);
    		}
    		TreeNode* root = new TreeNode(val);               //构建根结点
    		if (**str == '\0')
    			return root;
    		else
    			++(*str);
    		root->left = deserialize(str);                    //递归的构建左子树结点
    		root->right = deserialize(str);                   //递归的构建右子树结点
    		return root;
    	}
    };

[Center]: https://img-blog.csdn.net/20170419102043455?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvWUZfTGkxMjM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Image 1]: