Very intuitive solution in C, well-explained


  • 1

    Using pre-order to serialise and deserialise will be an instinctive solution and meantime we can take advantage of the conciseness of recursion to focus on the serialisation and deserialisation instead of too many details, especially in C.

    Here are two different versions, the first is to use a customised split function to split the serialised string first before actually deserialise while the second is just using pointer to move around to handle the number splitted by comma.

    • space cost O(n);
    • time cost O(n) since we just traverse the string several times.

    #define LEN 100    
    char* serialize(struct TreeNode* root)
    {
        if(!root) return "X,";
        char *t = (char*)malloc(sizeof(char)*LEN);
        int size = 0;
        int val = root->val;
        while(val) //collect the string and convert it number in reverse order;
        {
            t[size++] = val%10 + '0';
            val /= 10;
        }
        for(int i = 0; i < size/2; i++) //since it's reversed, then reverse it again to make it normal;
        {
            char c = t[size-i-1]; t[size-i-1]=t[i]; t[i]=c;
        }
        t[size++] = ','; //add splitter;
        t[size] = '\0'; //terminate the string;
        char *left = serialize(root->left); //collect left and right children;
        char *right = serialize(root->right);
        int leftSize = strlen(left);
        int rightSize = strlen(right);
        t = (char*)realloc(t, sizeof(char)*(size+leftSize+rightSize+2));
        strcat(t, left);
        strcat(t, right);
        return  t;
    }
    
    char** split(char* s, int* size) //split a string by ',';
    {
        char** arr = (char**)malloc(sizeof(char*));
        *size = 0;
        char* t = (char*)malloc(sizeof(char)*30);
        int index = 0;
        for(int i = 0; s[i]; i++)
        {
            if(s[i] != ',')
                t[index++] = s[i];
            else
            {
                t[index] = '\0';
                *size += 1;
                arr = (char**)realloc(arr, sizeof(char*)*(*size));
                arr[*size-1] = t;
                t = (char*)malloc(sizeof(char)*30);
                index = 0;
            }
        }
        return arr;
    }
    
    struct TreeNode* helper(char*** arr) //using the pointer of the array to move it for recursion;
    {
        if(strcmp(**arr, "X") == 0) return NULL;
        int num = 0;
        for(int i = 0; (**arr)[i]; i++)
            num = 10*num + (**arr)[i]-'0';
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = num;
        *arr += 1; //move to skip the current number;
        root->left = helper(arr);
        *arr += 1; //skip the left number;
        root->right = helper(arr);
        return root;
    }
    struct TreeNode* deserialize(char *s)
    {
        int size = 0;
        char** arr = split(s, &size);
        return helper(&arr);
    }
    

    The first version can be a little tedious, let's now take a look at the version 2 which only move the string pointer around to avoid the splitting operation and as a result it will also definitely quicker.


    #define LEN 100
    
    char* serialize(struct TreeNode* root)
    {
        if(!root) return "X,";
        char *t = (char*)malloc(sizeof(char)*LEN);
        int size = 0;
        int val = root->val;
        while(val) //collect the string and convert it number in reverse order;
        {
            t[size++] = val%10 + '0';
            val /= 10;
        }
        for(int i = 0; i < size/2; i++) //since it's reversed, then reverse it again to make it normal;
        {
            char c = t[size-i-1]; t[size-i-1]=t[i]; t[i]=c;
        }
        t[size++] = ','; //add splitter;
        t[size] = '\0'; //terminate the string;
        char *left = serialize(root->left); //collect left and right children;
        char *right = serialize(root->right);
        int leftSize = strlen(left);
        int rightSize = strlen(right);
        t = (char*)realloc(t, sizeof(char)*(size+leftSize+rightSize+2));
        strcat(t, left);
        strcat(t, right);
        return  t;
    }
    
    struct TreeNode* helper(char** s)
    {
        if(**s == 'X') return NULL; 
        int num = 0;
        int count = 0;
        while(**s != ',') //collect number and meantime skip the current number;
            num = 10*num + *((*s)++) - '0';
        *s += 1; //skip the comma ',';
        struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = num;
        root->left = helper(s);
        while((*(*s)++) != ','); //skip the left value;
        root->right = helper(s);
        retrn root;
    }
    
    struct TreeNode* deserialize(char* s)
    {
        return helper(&s);
    }

  • 0

    Actually the second solution can still be further optimised by storing the length of the string of the sub-tree which can accelerate the time by another 4ms.


    #define LEN 20
    char* serializeHelper(struct TreeNode* root, int* len)
    {
        *len = 2;
        if(!root) return "X,"; //convert null node to X ended with comma;
        char *t = (char*)malloc(sizeof(char)*LEN);
        int size = 0;
        int val = root->val;
        while(val) //invert integer to string;
        {
            t[size++] = val%10 + '0';
            val /= 10;
        }
        for(int i = 0; i < size/2; i++) //revert the string;
        {
            char c = t[size-i-1]; t[size-i-1]=t[i]; t[i]=c;
        }
        t[size++] = ','; //ended with comma as splitter;
        t[size] = '\0';
        int leftLen=0, rightLen=0;
        char *left = serializeHelper(root->left, &leftLen);
        char *right = serializeHelper(root->right, &rightLen);
        *len = size+leftLen+rightLen+2;
        t = (char*)realloc(t, sizeof(char)*(*len));
        strcat(t, left);
        strcat(t, right);
        return  t;
    }
    
    //AC - 16ms;
    char* serialize(struct TreeNode* root)
    {
        int len = 0;
        return serializeHelper(root, &len);
    }
    
    //modifying the string pointer is the core of this method;
    struct TreeNode* helper(char** s)
    {
        if(**s == 'X') return NULL;
        int num = 0;
        while(**s != ',') 
            num = 10*num + *((*s)++) - '0';
        *s += 1; //move the pointer to the start of the left sub-tree;
        struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = num;
        root->left = helper(s); //the pointer has moved past the left sub-tree;
        while(*((*s)++) != ','); //skip the last number of the left sub-tree, moving the pointer to the start of the right sub-tree;
        root->right = helper(s);
        return root;
    
    }
    
    struct TreeNode* deserialize(char* s)
    {
        return helper(&s); //using pointer to the pointer to move the pointer;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.