题解 | #序列化二叉树#

一.题意整理

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

1.二叉树的序列化是指：

把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点，以某个符号表示一个结点值的结束。

2.二叉树的反序列化是指：

根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

二.思路整理

序列化：
按照层次遍历将每个节点加入字符串中，当遇到空节点则加入null。
反序列化：
同样按照层次遍历的思想，首先构造头节点，然后再遍历节点的同时构造其左右子节点并入队列，当队列为空时，反序列化完毕。

题目对于遍历后的序列没有太大的要求，所以我们可以任意采用遍历方式。这里我们使用先序遍历的方式序列化二叉树，用' # '表示空，' * ' 标志一个结点值的结束，序列化时通过先序遍历的顺序，当遇到非空节点时取出其值的字符串表示再在后面加个'!'标示着结尾，以便我们反序列化时确定节点的值出于代码编写的遍历，我们先用string记录得到序列，再利用c_str()转换为题目要求的 char* 字符串。

三.代码实现

class Solution {
public:
    //先序遍历利用string记录先序序列
    void inorder(TreeNode *root,string& s){
        if(root==nullptr){
            s+="#";
            return;
        }
        s+=to_string(root->val)+"*";
        inorder(root->left,s);
        inorder(root->right,s);
    }
    //返回先序遍历的字符串
    char* Serialize(TreeNode *root) {
        string s;
        inorder(root,s);
        char* ans = new char[105];
        strcpy(ans,s.c_str());
        return ans;
    }

    TreeNode* deserialize(char *s, int& cnt){
        if(s[cnt]=='#'){
            cnt++;
            return nullptr;
        }
        //判断是否是负数
        bool ck=1;
        if(s[cnt]=='-'){
            ck=0;
            cnt++;
        }
        int num=0;
        //对字符串中的数进行提取
        while(s[cnt]!='*'){
            num=num*10+s[cnt]-'0';
            cnt++;
        }
        if(!ck) num-=num;
        cnt++;
        TreeNode* root = new TreeNode(num);
        //递归
        root->left = deserialize(s,cnt);
        root->right = deserialize(s,cnt);
        return root;
    }

    TreeNode* Deserialize(char *str) {
        int now=0;
        //返回反序列化的值
        return deserialize(str,now);
    }
};