Very intuitive solution accepted as best in C, well-explained


  • 0

    At first, just for a try I personally wrote a split function to split the string separated by comma and the result turned out not pretty bad compared with the current best submission. But actually as you anticipate that we can just save that kind of cost and reach out for the best directly checking the comma and the character just before it or when we hit the end '\0' of the string we can also check the character just before it. Needless to split indeed ^^

    Okay, now let's do some analysis on this problem:

    • the serialisation string of a preorder binary tree;
    • one rule for sure is that the children of a node must be after itself which indirectly means the amount of null can only be in its children; and the more children we are to cover the amount of null should be bigger;
    • another rule is that the amount of null in a tree is just bigger than the amount of not-null node by one just by one;
    • then the conclusion can be this before the end of the preorder string:

    the amount of null can not surpass the amount of not-null nodes by 1 and meantime when we reach the end, the difference should be exactly 1.

    Bang! End of Story!

    • space cost O(1)
    • time cost O(n)

    //AC - 0ms;
    bool isValidSerialization(char* preorder)
    {
        int difference = 0;
        int size = strlen(preorder);
        for(int i = 1; i <= size; i++)
        {
            if(preorder[i]==',' || preorder[i]=='\0') 
            {
                if(preorder[i-1] == '#') //null;
                    difference++;
                else //not null; 
                    difference--;
            }
            if(difference > 1) return false; //surpass more than 1, return false directly;
            if(difference==1 && i!=size) return false; //not end of the string but it reaches difference 1 already, terminate the checking directly;
        }
        if(difference < 1) return false; //after traversing the difference should be exactly one;
        return true;
    }
    

    There is also enclosed with my another version using personal split function to split the string first which also accepted in a pretty good performance 8ms.


    char** split(char* s, int* size)
    {
        char** arr = (char**)malloc(sizeof(char*));
        char *t = (char*)malloc(sizeof(char)*30); 
        int index = 0;
         for(int i = 0; i < strlen(s)+1; i++)
        {
           if(s[i]==',' || s[i]=='\0')
            {
                if(s[i]==',' || s[i]=='\0')
                {
                    t[index] = '\0';
                    *size += 1;
                    arr = (char**)realloc(arr, sizeof(char*)*(*size));
                    arr[*size-1] = t;
                }
                index = 0;
                t = (char*)malloc(sizeof(char)*30);
            }
            else
            {
                t[index++] = s[i];
            }
        }
        return arr;
    }
    
    //AC - 8ms;
    bool isValidSerialization(char* preorder)
    {
        int size = 1;
        char** arr = split(preorder, &size);
        int difference = 0;
        for(int i = 1; i < size; i++)
        {
            if(strcmp(arr[i], "#") == 0) //it's null;
                difference++;
            else //it's null cannot have not-null children;
                difference--;
            if(difference>1 || (difference==1&&i!=size-1)) return false;
        }
        if(difference < 1) return false;
        return true;
    }

Log in to reply
 

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