這題好難，偷看了一下解答
我這輩子就這樣了
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]]