310. 最小高度树

310. 最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[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;



}