剩我圣诞夜还在解题了
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]

今天好难

之前有类似的