对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例 1:
代码语言：javascript复制输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/
2 3
输出: [1]示例 2:
代码语言：javascript复制输入: 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时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点
代码实现
代码语言：javascript复制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
}
