题解 | #序列化二叉树#

1.思路：

序列化即将二叉树的节点值取出，放入一个字符串中，我们可以按照前序遍历的思路，遍历二叉树每个节点，并将节点值存储在字符串中，我们用‘#’表示空节点，用‘!'表示节点与节点之间的分割。

反序列化即根据给定的字符串，将二叉树重建，因为字符串中的顺序是前序遍历，因此我们重建的时候也是前序遍历，即可还原。

具体做法：

• step 1：优先处理序列化，首先空树直接返回“#”，然后调用SerializeFunction函数前序递归遍历二叉树。
• step 2：SerializeFunction函数负责前序递归，根据“根左右”的访问次序，优先访问根节点，遇到空节点在字符串中添加‘#’，遇到非空节点，添加相应节点数字和‘!’，然后依次递归进入左子树，右子树。
• step 3：创建全局变量index表示序列中的下标（C++中直接指针完成）。
• step 4：再处理反序列化，读入字符串，如果字符串直接为"#"，就是空树，否则还是调用DeserializeFunction函数前序递归建树。
• step 5：DeserializeFunction函数负责前序递归构建树，遇到‘#’则是空节点，遇到数字则根据感叹号分割，将字符串转换为数字后加入新创建的节点中，依据“根左右”，创建完根节点，然后依次递归进入左子树、右子树创建新节点。

复制代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    //处理序列化的功能函数（前序）
    string serialize(TreeNode* root)
    {
        //如果指针为空，表示左子节点或右子节点为空，用#表示
        //'!'用来区分每一个结点
        if(!root)
            return "#!";
        string str;
        //记录根节点
        str = to_string(root->val) + "!";
        //递归记录左子树
        str += serialize(root->left);
        //递归记录右子树
        str += serialize(root->right);
        return str;
    }
    //处理反序列化的功能函数
    //char*类型的引用形参，每次调用会改变该指针指向的地址，即指向不同的数，以实现访问数组中的元素
    TreeNode* deserialize(char* &str)
    {
        //前序
        //到达叶节点时，构建完毕，返回继续构建父节点
        if(*str == '#')
        {
            str++;
            return nullptr;
        }
        //数字转换
        int num = 0;
        while(*str != '!')
        {
            num = num*10+*str-'0';
            str++;
        }
        TreeNode* node = new TreeNode(num);
        //如果序列到底了，构建完成
        if(*str == '\0')
            return node;
        //递归添加左右子树
        node->left = deserialize(++str);
        node->right = deserialize(++str);
        return node;
    }
public:
    char* Serialize(TreeNode *root)
    {
        string str = serialize(root);
        char* res = new char[str.size()+1];
        //把string转换为char
        for(int i = 0;i<str.size();i++)
            res[i] = str[i];
        res[str.size()] = '\0';
        return res;
    }
    TreeNode* Deserialize(char *str)
    {
        return deserialize(str);
    }

};