310. minimum height tree

310. Minimum height tree

A tree is an undirected graph , Any two of these vertices are connected by only one path . let me put it another way , Any connected graph without simple loops is a tree .

Give you a tree that contains n Tree of nodes , Marked as 0 To n - 1 . Given number n And one with n - 1 An undirected edge edges list （ Each side is a pair of labels ）, among edges[i] = [ai, bi] Represents the node in the tree ai and bi There is an undirected edge between .

You can select any node in the tree as the root . When selecting a node x As the root node , Let the height of the result tree be h . In all possible trees , Tree with minimum height （ namely ,min(h)） go by the name of Minimum height tree .

Please find all Minimum height tree And press In any order Return a list of their root node labels .
Treelike Height It refers to the number of edges on the longest downward path between the root node and the leaf node .

Example 1：

Input ：n = 4, edges = [[1,0],[1,2],[1,3]]
Output ：[1]
explain ： As shown in the figure , When the root is labeled 1 The nodes of , The height of the tree is 1 , This is the only minimum height tree .

Example 2：

Input ：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output ：[3,4]

/** * Note: The returned array must be malloced, assume caller calls free(). */
int min_h;

int dfs( int** edges, int edgesSize,int now_node,int h,int *r,int *rs){
    
    
        int i=0;
       int maxh=0;
       int num=0;
        for(i;i<edgesSize;i++){
    
            if(edges[i][0]==now_node&&r[edges[i][1]]==0){
    
               
                 r[edges[i][1]]=1;
               int max1= dfs(edges,edgesSize,edges[i][1],h+1,r,rs);
                if(max1>maxh){
    
                   maxh=max1;
               }
               
            
              
                 r[edges[i][1]]=0;
            }
             if(edges[i][1]==now_node&&r[edges[i][0]]==0){
    
                
                  r[edges[i][0]]=1;
                 int max1= dfs(edges,edgesSize,edges[i][0],h+1,r,rs);

                    if(max1>maxh){
    
                   maxh=max1;
               }
              
                 
                 r[edges[i][0]]=0;
             }
            
        }
        if(maxh==0){
    
            return h;
        }
        else{
    
            return maxh;
        }
       


}


int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize){
    
    int r[n];
    int rs[n];
    int i;
    int *re=(int *)malloc(sizeof(int)*n);
    for(i=0;i<n;i++){
    
        r[i]=0;
        rs[i]=0;
    }
    
   int min=1000;
    for(i=0;i<n;i++){
    
        if(rs[i]!=0){
    
             if(rs[i]<min){
    
                min=rs[i];
            
            }
            continue;

        }
           r[i]=1;
              int h2=dfs(edges,edgesSize,i,1,r,rs);
             rs[i]=h2;
            
            if(h2<min){
    
                min=h2;
            
            }
              

                r[i]=0;
               
    }
printf("min %d ",min);
    int size=0;
     for(i=0;i<n;i++){
    
           printf("%d| ",rs[i]);
            if(rs[i]==min){
    
               re[size++]=i;
            
            }
               
               
    }
  
    * returnSize=size;
    return re;



}