【剑指offer】序列化二叉树（二叉树）

题目描述

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

思路

将问题分解为左子树、根节点、右子树分别进行递归处理。

序列化是从根开始的，那么对应的反序列化在根节点的先序遍历中就可以得到。用’#'表示遍历过程中的nullptr，通过先序遍历得到序列。
如：0,1,3,###2,4,##5,##

反序列化：
如上式，首先得到数字0，作为根节点；然后得到数字1，是根节点的左子节点，接着得到3，是1的左子节点；接着得到两个’#‘,说明3为叶子结点，左右孩子都是空。然后得到’#’,说明1的右子节点为空；接着得到2，说明0的右子节点为2；以此类推。

代码

/*
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 == nullptr){
            return "#";
        }

        string s = to_string(root->val);
        s.push_back(',');
        char *left = Serialize(root->left);
        char *right = Serialize(root->right);
        char *ret = new char[strlen(left) + strlen(right) + s.size()];
        strcpy(ret,s.c_str());
        strcat(ret,left);
        strcat(ret,right);
        return ret;
    }
    // 注意参数类型应该为char *&str
    TreeNode* Deserialize(char *&str) {
        if (*str == '#'){
            str ++;
            return nullptr;
        }
        int num = 0;
        while (*str!=','){
            num = num * 10 + (*(str++) - '0');
        }
        str ++; // 跳过','
        TreeNode *root = new TreeNode(num);
        root->left = Deserialize(str);
        root->right = Deserialize(str);
        return root;
    }
};