Though the OJ is not that ideal, another solution comes to me now beating 100% submission in C


  • 1

    Okay, just hit the road! Since we are required to search for the Minimal Height Trees and return the roots that meet the requirements -> instincts give us a hint -> level traversal until the end level -> which will at most contain 2 nodes, otherwise it will not be the end level (or you may say top level ) in a tree. My previous solution though is very intuitive but tumbles into weird TLE which I also post a OJ judgement problem here.

    At first I tried to use a customised hash-set to handle the performance problem in the innermost loop of that solution. But soon I found out that actually I do not need to remove the vertexes at all using another array to record the states of the degrees of each vertex can be completely enough. So here is my optimised version of my former solution using degrees to record the states of the vertexes which also result in beating all submissions in C with 1044ms. All the specifics are presented in comments, since you're using C you must think it good enough ^^.

    Bang! Happy Day!

    • space cost O(n*m), most of the cost is recording the edges list transforming the provided edges;
    • time cost O(E) the whole process is removing edges until there are several of them;

    int* findMinHeightTrees(int n, int** edges, int rSize, int cSize, int* returnSize)
    {
        int* arr = (int*)malloc(sizeof(int)*n);
        *returnSize = 0;
        if(n == 1) //corner case;
        {
            *returnSize += 1;
            arr[*returnSize-1] = 0;
            return arr;
        }
        int** graph = (int**)malloc(sizeof(int*)*n); //constructing the graph as a DAG - Directed Acyclic Graph;
        for(int i = 0; i < n; i++)
            graph[i] = (int*)malloc(sizeof(int));
        int* colSizes = (int*)malloc(sizeof(int)*n);
        memset(colSizes, 0, sizeof(int)*n);
        for(int i = 0; i < rSize; i++) //constructing the graph in edges list format;
        {
            int begin = edges[i][0];
            int end = edges[i][1];
            colSizes[begin]++;
            graph[begin] = (int*)realloc(graph[begin], sizeof(int)*colSizes[begin]); //dynamically allocate the space - just use the required space, nothing more;
            graph[begin][colSizes[begin]-1] = end;
            colSizes[end]++;
            graph[end] = (int*)realloc(graph[end], sizeof(int)*colSizes[end]);
            graph[end][colSizes[end]-1] = begin;
        }
        int* degrees = (int*)malloc(sizeof(int)*n);
        for(int i = 0; i < n; i++) //collecting the bottom leaves;
        {
            degrees[i] = colSizes[i]; //copy the degrees;
            if(colSizes[i] == 1)
            {
                *returnSize += 1;
                arr[*returnSize-1] = i;
            }
        }
        int count = n; //record the vertexes left;
        int* nextLevel = (int*)malloc(sizeof(int)*n); //used with arr imitating queue operations;
        int next = 0;
        while(count > 2)
        {
            for(int i = 0; i < *returnSize; i++)
            {
                int end = arr[i];
                count--; //remove the leaf then the vertexes left should be decremented;
                for(int k = 0; k < colSizes[end]; k++) //decrement related vertexes in degrees;
                {
                    int begin = graph[end][k];
                    degrees[begin]--;
                    if(degrees[begin] == 1) //when the degree of the connected vertex is 1 which means it turns leaf now, collect it for next level;
                        nextLevel[next++] = graph[end][k];
                }
            }
            *returnSize = next; //update next, returnSize, arr and nextLevel for next round;
            next = 0;
            int *t=arr; arr=nextLevel; nextLevel=t;
        }
        return arr;
    }
    

Log in to reply
 

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