序列化二叉树

序列化二叉树

题目描述

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

题意没明白, 想了半天, 明白题意又不知道怎么解, 又想了半天, 看了答案没懂, 又是半天, 哎...

class Solution {
public:
    void Serialize(TreeNode *root, string &str) {
        if (root == nullptr) {
            str += '#';
            return;
        }
       
        str += to_string(root->val);;
        str += ',';    // 用来分隔数字, 否则多位数字时没法区分
        Serialize(root->left, str);
        Serialize(root->right, str);
    }
    
    char* Serialize(TreeNode *root) {    
        if (nullptr == root)
            return nullptr;
        
        string str;    // 要保存的字符串
        Serialize(root, str);
        
        char *p = new char[str.length()+1];    // 多一个字符用来保存
        for (int i = 0; i < str.length(); i++) {
            p[i] = str[i];
        }
        p[str.length()] = '';
        return p;
    }
    
    TreeNode* Deserialize(char **str) {    // 使用二级指针用来移动str的位置
        if ('#' == (**str)) {
            (*str)++;
            return nullptr;
        }
        
        int num = 0;    // 字符串转数字
        while (('' != **str) && ((**str) != ',')) {
            num = num * 10 + (**str) - '0';    // 多位数字要乘10
            (*str)++;
        }
        
        TreeNode *root = new TreeNode(num);
        
        if(**str == '')    // 判断是否结束
            return root;
        else                 // 越过逗号分隔符
            (*str)++;
        
        root->left = Deserialize(str);
        root->right = Deserialize(str);
        return root;
    }
    
    TreeNode* Deserialize(char *str) {
        if (nullptr == str)
            return nullptr;
        TreeNode *ret;
        ret = Deserialize(&str);
        return ret;
    }
};

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