剩我聖誕夜還在解題了
3203. Find Minimum Diameter After Merging Two Trees
思路
就將每棵樹的各個節點的indegree算出來
接著將indegree=1的節點丟到queue裡
從queue裡pop出indegree=1的節點
把與它相連的node indegree都-1
如果indegree=1且之前沒有遇到就push到queue裡
這樣可以算出這棵樹的level
如果最後一次queue的長度大於1
那就把level++
最後回傳level
再來去算兩棵樹各自兩點間相隔最長的路徑length1、length2
答案就會是max(level1+level2,length1,length2)
golang code :
func minimumDiameterAfterMerge(edges1 [][]int, edges2 [][]int) int {
indegree1, path1 := calindegree(edges1)
indegree2, path2 := calindegree(edges2)
level1, length1 := callevel(indegree1, path1)
level2, length2 := callevel(indegree2, path2)
return max(length1, length2, level1+level2+1)
}
func calindegree(edge [][]int) ([]int, [][]int) {
n := len(edge) + 1
res := make([]int, n)
path := make([][]int, n)
for i := 0; i < n; i++ {
path[i] = []int{}
}
for _, val := range edge {
res[val[0]]++
path[val[0]] = append(path[val[0]], val[1])
res[val[1]]++
path[val[1]] = append(path[val[1]], val[0])
}
return res, path
}
func callevel(indegree []int, path [][]int) (int, int) {
queue := []int{}
visit := make([]bool, len(indegree))
for key, val := range indegree {
if val == 1 {
queue = append(queue, key)
visit[key] = true
}
}
tmp := 0
level := -1
for len(queue) > 0 {
cnt := len(queue)
level++
tmp = cnt
for cnt > 0 {
node := queue[0]
queue = queue[1:]
for _, val := range path[node] {
indegree[val]