2025-02-11：合并两棵树后的最小直径。用go语言，给定两棵无向树，第一棵树有 n 个节点，第二棵树有 m 个节点，节点编

福大大架构师每日一题

发布于 2025-02-12 15:37:01

12900

运行总次数：0

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)