题解 | #序列化二叉树#

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return char字符型一维数组
 */
char* Serialize(struct TreeNode* root ) {
    // write code here
    char* str=(char*)malloc(sizeof(char)*1000);
    if(!root) return "\0";
     struct TreeNode **queue = (struct TreeNode**) malloc(100 * sizeof(struct TreeNode*));
    struct TreeNode *cur = NULL;
    int i = 0, j = 0,m=0;
    queue[j++] = root;
    int n=root->val;
    if(n/100>0){str[m++]='0'+n/100;}
    if(n/10>0){str[m++]='0'+n%100/10;}
    str[m++]='0'+n%10;//0<=val<=150
    while(i<j){//层序遍历整个二叉树
        int last=j;
        while(i<last){
            cur = queue[i++];
            if(cur->left) {
                queue[j++]=cur->left;
                str[m++]=',';
                n=cur->left->val;
                if(n/100>0){str[m++]='0'+n/100;}
                if(n/10>0){str[m++]='0'+n%100/10;}
                str[m++]='0'+n%10;
            }
            else{
                str[m++]=',';
                str[m++]='#';
            }
            if(cur->right) {
                queue[j++]=cur->right;
                str[m++]=',';
                n=cur->right->val;
                if(n/100>0){str[m++]='0'+n/100;}
                if(n/10>0){str[m++]='0'+n%100/10;}
                str[m++]='0'+n%10;
            }
            else{
                str[m++]=',';
                str[m++]='#';
            }
        }
    }
    --m;
    while(str[m]==','||str[m]=='#') --m;
    str[++m]='\0';
    return str;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str char字符型一维数组 
 * @return TreeNode类
 */
struct TreeNode* Deserialize(char* str ) {
    // write code here
    int numsLen =strlen(str);
    struct TreeNode* q[100];
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    if(numsLen==0) return NULL;
    int i=0, frist=0, end=0;
    int n=str[i]-'0';
    while(str[i+1]!=','&&str[i+1]!='\0')n=n*10+str[++i]-'0';
    root->val = n;
     i=i+2;//直接用字符串赋值，每次索引加2
    q[end++]=root;
     
    while(frist<end && i<numsLen){
        struct TreeNode* ans = q[frist++];
        if(str[i]=='#'){
            ans->left = NULL;
            i+=2;
        }
        else{
            ans->left = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
            n=str[i]-'0';
            while(str[i+1]!=','&&str[i+1]!='\0')n=n*10+str[++i]-'0';
            ans->left->val =n;
            i+=2;
            q[end++]=ans->left;
        }
        if(i>=numsLen) break;
        if(str[i]=='#'){
            ans->right = NULL;
            i+=2;
        }
        else{
            ans->right = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
            n=str[i]-'0';
            while(str[i+1]!=','&&str[i+1]!='\0')n=n*10+str[++i]-'0';
            ans->right->val = n;
            i+=2;
            q[end++]=ans->right;
        }
    }
    return root;
}