Golang | Leetcode Golang题解之第310题最小高度树

题目：

题解：

func findMinHeightTrees(n int, edges [][]int) []int {
    if n == 1 {
        return []int{0}
    }
 
    g := make([][]int, n)
    deg := make([]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
        deg[x]++
        deg[y]++
    }
 
    q := []int{}
    for i, d := range deg {
        if d == 1 {
            q = append(q, i)
        }
    }
 
    remainNodes := n
    for remainNodes > 2 {
        remainNodes -= len(q)
        tmp := q
        q = nil
        for _, x := range tmp {
            for _, y := range g[x] {
                deg[y]--
                if deg[y] == 1 {
                    q = append(q, y)
                }
            }
        }
    }
    return q
}