这题好难，偷看了一下解答
我这辈子就这样了
310. Minimum Height Trees
有一个无向图，两个节点间只有一条路径
该图有n个节点:0~n-1，以及n-1条路径
去找最小高度树，并回传所有最小高度树的root
思路 :
首先叶子节点不可能是MHT的root
原因可以看这篇 : https://home.gamer.com.tw/artwork.php?sn=5478747
所以就从叶子节点开始去除
并记录这么做后有哪些节点变成叶子节点
这样一直做之后
最后变成叶子节点的节点就是MHT的root
golang code:
func findMinHeightTrees(n int, edges [][]int) []int {
count:=make([]int,n)
link:=make([]int,n)
for _,val:=range edges{
//a^0=a
link[val[0]]^=val[1]//纪录连接的点
count[val[0]]++
link[val[1]]^=val[0]//纪录连接的点
count[val[1]]++
}
queue:=[]int{}
for key,val:=range count{
if val==1{
queue=append(queue,key)
}
}
step:=1
dist:=make([]int,n)
cnt:=len(queue)
maxdist:=0
for len(queue)>0{
for cnt>0{
//叶子节点 只有一个连接node,所以link[temp]就是与该叶子节点连接的节
点
temp:=queue[0]
queue=queue[1:]
//把与该叶子节点连结的节点link记录去除该叶子节点
//(a^b^c)^a=(b^c)
link[link[temp]]^=temp
count[link[temp]]