2025-02-11：合并两棵树后的最小直径。用go语言，给定两棵无向树，第一棵树有 n 个节点，第二棵树有 m 个节点，节点编
2025-02-11：合并两棵树后的最小直径。用go语言，给定两棵无向树，第一棵树有 n 个节点，第二棵树有 m 个节点，节点编
2025-02-11：合并两棵树后的最小直径。用go语言，给定两棵无向树，第一棵树有 n 个节点，第二棵树有 m 个节点，节点编号分别为 0 到 n-1 和 0 到 m-1。每棵树的边信息通过二维数组 edges1 和 edges2 表示，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间存在一条边，而 edges2[i] = [ui, vi] 则表示第二棵树中节点 ui 和 vi 之间有一条边。
你的任务是从每棵树中选择一个节点，并通过一条新边将这两个节点连接起来。最终，你需要返回添加这条边之后新形成的树的最小直径。
在此，树的直径定义为任意两个节点之间的最长路径长度。
1 <= n, m <= 100000。
edges1.length == n - 1。
edges2.length == m - 1。
edges1[i].length == edges2[i].length == 2。
edges1[i] = [ai, bi]。
0 <= ai, bi < n。
edges2[i] = [ui, vi]。
0 <= ui, vi < m。
输入保证 edges1 和 edges2 分别表示一棵合法的树。
输入：edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]。
输出：3。
解释：
将第一棵树中的节点 0 与第二棵树中的任意节点连接，得到一棵直径为 3 的树。
答案2025-02-11：
chatgpt
题目来自leetcode3203。
大体步骤如下：
1.定义一个函数 diameter 用于计算树的直径。首先，构建两个邻接表 g 分别存储两棵树的边关系。然后定义一个递归内部函数 dfs 用于进行深度优先搜索（DFS）。
2.在 dfs 函数中，通过递归遍历树的节点，计算每个非父节点到根节点的最长路径。在遍历过程中更新直径的长度。
3.计算第一棵树和第二棵树的直径分别为 d1 和 d2。
4.计算合并后树的直径：
- • 如果将两棵树通过一条边直接相连，直径为两棵树直径的最大值。
- • 否则，考虑通过一个节点连接两棵树，直径为
(d1+1)/2 + (d2+1)/2 + 1。
5.输出返回合并后树的最小直径。
总的时间复杂度：
- • 构建邻接表：O(n + m)，其中 n 和 m 分别代表两棵树的节点数目。
- • 计算两棵树的直径：O(n + m)。
- • 计算合并后树的直径：O(1)。
总的额外空间复杂度：
- • 邻接表存储：O(n + m)。
- • 递归调用栈：O(n + m)。
Go完整代码如下：
package main
import (
"fmt"
)
func diameter(edges [][]int) (res int) {
g := make([][]int, len(edges)+1)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
var dfs func(int, int)int
dfs = func(x, fa int) (maxLen int) {
for _, y := range g[x] {
if y != fa {
subLen := dfs(y, x) + 1
res = max(res, maxLen+subLen)
maxLen = max(maxLen, subLen)
}
}
return
}
dfs(0, -1)
return
}
func minimumDiameterAfterMerge(edges1, edges2 [][]int)int {
d1 := diameter(edges1)
d2 := diameter(edges2)
return max(d1, d2, (d1+1)/2+(d2+1)/2+1)
}
func main() {
edges1 := [][]int{{0, 1}, {0, 2}, {0, 3}}
edges2 := [][]int{{0, 1}}
result := minimumDiameterAfterMerge(edges1, edges2)
fmt.Println(result)
}
Rust完整代码如下：
use std::cmp;
fndiameter(edges: Vec<Vec<i32>>) ->i32 {
letn = edges.len() + 1;
letmut g = vec![Vec::new(); n];
foredgein edges {
letx = edge[0];
lety = edge[1];
g[x asusize].push(y);
g[y asusize].push(x);
}
letmut res = 0;
fndfs(x: i32, fa: i32, g: &Vec<Vec<i32>>, res: &muti32) ->i32 {
letmut max_len = 0;
for &y in &g[x asusize] {
if y != fa {
letsub_len = dfs(y, x, g, res) + 1;
*res = cmp::max(*res, max_len + sub_len);
max_len = cmp::max(max_len, sub_len);
}
}
max_len
}
dfs(0, -1, &g, &mut res);
res
}
fnminimum_diameter_after_merge(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) ->i32 {
letd1 = diameter(edges1);
letd2 = diameter(edges2);
cmp::max(d1, cmp::max(d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1))
}
fnmain() {
letedges1 = vec![vec![0, 1], vec![0, 2], vec![0, 3]];
letedges2 = vec![vec![0, 1]];
letresult = minimum_diameter_after_merge(edges1, edges2);
println!("{}", result);
}
Python完整代码如下：
# -*-coding:utf-8-*-
defdiameter(edges):
n = len(edges) + 1
g = [[] for _ inrange(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
res = 0
defdfs(x, fa):
nonlocal res
max_len = 0
for y in g[x]:
if y != fa:
sub_len = dfs(y, x) + 1
res = max(res, max_len + sub_len)
max_len = max(max_len, sub_len)
return max_len
dfs(0, -1)
return res
defminimum_diameter_after_merge(edges1, edges2):
d1 = diameter(edges1)
d2 = diameter(edges2)
returnmax(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1)
if __name__ == "__main__":
edges1 = [[0, 1], [0, 2], [0, 3]]
edges2 = [[0, 1]]
result = minimum_diameter_after_merge(edges1, edges2)
print(result)
腾讯云开发者
