Search
🥈

Minimum Height Trees

Created
2021/12/17 15:05
문제 번호
310
카테고리
Depth-First Search
Breadth-First Search
Graph
Topological Sort

Code

제출 날짜
시간
메모리
2021/12/17
36 ms
8.2 MB
// 310. Minimum Height Trees // // https://leetcode.com/problems/minimum-height-trees/ // findMinHeightTrees function finds the possible root nodes which has the minimum height. // Finding the longest path of the tree by DFS can be possible, but topological sort is more suitable. // To find the minimum height, remove the possible leaf nodes by iterative loop. // Removing leaf nodes can be done by looking up the edges. // Also the iterating should be stopped when the existing nodes are less than or equal to 2. func findMinHeightTrees(n int, edges [][]int) []int { if n == 1 { return []int{0} } graph := make(map[int][]int, n) count := make([]int, n) for _, e := range edges { if _, ok := graph[e[0]]; !ok { graph[e[0]] = make([]int, 0) } if _, ok := graph[e[1]]; !ok { graph[e[1]] = make([]int, 0) } graph[e[0]] = append(graph[e[0]], e[1]) graph[e[1]] = append(graph[e[1]], e[0]) count[e[0]]++ count[e[1]]++ } leaves := make([]int, 0) for i, c := range count { if c == 1 { leaves = append(leaves, i) } } for n > 2 { size := len(leaves) n -= size for i := 0; i < size; i++ { count[leaves[i]]-- for _, c := range graph[leaves[i]] { count[c]-- if count[c] == 1 { leaves = append(leaves, c) } } } leaves = leaves[size:] } return leaves }
Go
복사