golang刷leetcode 经典（13） 最小高度树

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]


        0
        |
        1
       / \
      2   3 


输出: [1]

复制

示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]


     0  1  2
      \ | /
        3
        |
        4
        |
        5 


输出: [3, 4]

复制

说明:

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

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

解题思路

1，题目特点，一种特殊的图，没有环，不存在多根

2，一个类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点

3，对于图类型题目一边先建立邻接矩阵

4，我们开始将所有只有一个连接边的节点(叶节点)都存入到一个队列queue中

5，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，并且在其相连节点的集合中将该叶节点删去，

6，如果删完后此节点也也变成一个叶节点了，加入队列中，再下一轮删除。

7，那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点

代码实现

func findMinHeightTrees(n int, edges [][]int) []int {
     if len(edges)==0 || len(edges[0])==0{
         var r []int
         r=append(r,0)
         return r
     }
    adj:=make([][]int,n)
    for i:=0;i<len(edges);i++{
        adj[edges[i][0]]=append(adj[edges[i][0]],edges[i][1])
        adj[edges[i][1]]=append(adj[edges[i][1]],edges[i][0])
    }   

    //fmt.Println(adj)
     
     root,adj:=removeLeaf(adj,n)
     for len(root)>2{
        root,adj=removeLeaf(adj,n)
     }

    return root

}

func removeLeaf(adj [][]int,n int)([]int,[][]int){
     var leaf []int
     var root []int
    for i:=0;i<n;i++{
        if len(adj[i])==1{
            leaf=append(leaf,i)
            root=append(root,adj[i][0])//有重复的
            adj[i]=nil
        }
    }
   
    for j:=0;j<len(root);j++{
       adj[root[j]]=remove(adj[root[j]],leaf[j])
    }
   
    var root1 []int
    for i:=0;i<n;i++{
       if len(adj[i])>0{
            root1=append(root1,i)
        }
    }
    if len(root1)==0{
        for i:=0;i<len(root);i++{
            if !match(root[i],root1){
                root1=append(root1,root[i])
            }
        }
    }
    // fmt.Println(root,root1,adj)
    return root1,adj
}

func remove(adj[]int,v int)[]int{
     var adj1 []int
     if adj!=nil{
        for i:=0;i<len(adj);i++{
        if adj[i]==v{
            continue
        }
        adj1=append(adj1,adj[i])
        }
     }
   return adj1        
}

func match(v int,leaves []int)bool{
    for k:=0;k<len(leaves);k++{
        if v==leaves[k]{
            return true
        }
    }
    return false
}

复制