Hard
题目描述
存在两棵无向树，节点数分别为 n 和 m，节点编号分别为 0 到 n-1 和 0 到 m-1。给定两个二维整数数组 edges1 和 edges2，长度分别为 n-1 和 m-1，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。
你必须在第一棵树的一个节点和第二棵树的一个节点之间连接一条边。
返回合并后树的最小可能直径。
树的直径是树中任意两个节点之间最长路径的长度。
示例 1：
输入：edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]
输出：3
解释：我们可以通过连接第一棵树的节点 0 和第二棵树的任意节点得到直径为 3 的树。
示例 2：
输入：edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]], edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
输出：5
解释：我们可以通过连接第一棵树的节点 0 和第二棵树的节点 0 得到直径为 5 的树。
约束条件：
- 1 ≤ n, m ≤ 10^5
- edges1.length == n - 1
- edges2.length == m - 1
- edges1[i].length == edges2[i].length == 2
- 0 ≤ ai, bi < n
- 0 ≤ ui, vi < m
- 输入保证 edges1 和 edges2 表示有效的树
解题思路
这是一个关于树直径的经典问题。我们需要分析合并两棵树后的最小直径。
核心思路：
当我们在两棵树之间连接一条边时，新树的直径可能来自三种情况：
- 完全在第一棵树内
- 完全在第二棵树内
- 跨越两棵树（经过连接边）
前两种情况的值是固定的，就是原来两棵树的直径。关键是如何最小化第三种情况。
算法步骤：
计算树的直径：使用两次BFS/DFS的经典方法
- 从任意节点出发找到最远的节点A
- 从节点A出发找到最远的节点B
- A到B的距离就是直径
找到树的中心：对于一棵树，其中心是直径路径的中点。从中心到树中任意节点的最大距离是 ⌈直径/2⌉
计算最优连接：当我们连接两棵树的中心时，跨越连接边的最长路径是： ⌈diameter1/2⌉ + ⌈diameter2/2⌉ + 1
取最大值：合并后的最小直径是以下三者的最大值：
- diameter1
- diameter2
- ⌈diameter1/2⌉ + ⌈diameter2/2⌉ + 1
这种方法保证了我们选择最优的连接点来最小化合并后的直径。
代码实现
class Solution {
public:
int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
auto getDiameter = [](vector<vector<int>>& edges) -> int {
int n = edges.size() + 1;
if (n == 1) return 0;
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
auto bfs = [&](int start) -> pair<int, int> {
vector<int> dist(n, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
int farthest = start;
int maxDist = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
q.push(neighbor);
if (dist[neighbor] > maxDist) {
maxDist = dist[neighbor];
farthest = neighbor;
}
}
}
}
return {farthest, maxDist};
};
auto [node1, _] = bfs(0);
auto [node2, diameter] = bfs(node1);
return diameter;
};
int diameter1 = getDiameter(edges1);
int diameter2 = getDiameter(edges2);
int crossDiameter = (diameter1 + 1) / 2 + (diameter2 + 1) / 2 + 1;
return max({diameter1, diameter2, crossDiameter});
}
};
class Solution:
def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
def get_diameter(edges):
n = len(edges) + 1
if n == 1:
return 0
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def bfs(start):
dist = [-1] * n
queue = [start]
dist[start] = 0
farthest = start
max_dist = 0
for node in queue:
for neighbor in graph[node]:
if dist[neighbor] == -1:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
if dist[neighbor] > max_dist:
max_dist = dist[neighbor]
farthest = neighbor
return farthest, max_dist
node1, _ = bfs(0)
node2, diameter = bfs(node1)
return diameter
diameter1 = get_diameter(edges1)
diameter2 = get_diameter(edges2)
cross_diameter = (diameter1 + 1) // 2 + (diameter2 + 1) // 2 + 1
return max(diameter1, diameter2, cross_diameter)
public class Solution {
public int MinimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
int GetDiameter(int[][] edges) {
int n = edges.Length + 1;
if (n == 1) return 0;
var graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
(int, int) BFS(int start) {
var dist = new int[n];
Array.Fill(dist, -1);
var queue = new Queue<int>();
queue.Enqueue(start);
dist[start] = 0;
int farthest = start;
int maxDist = 0;
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int neighbor in graph[node]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
queue.Enqueue(neighbor);
if (dist[neighbor] > maxDist) {
maxDist = dist[neighbor];
farthest = neighbor;
}
}
}
}
return (farthest, maxDist);
}
var (node1, _) = BFS(0);
var (node2, diameter) = BFS(node1);
return diameter;
}
int diameter1 = GetDiameter(edges1);
int diameter2 = GetDiameter(edges2);
int crossDiameter = (diameter1 + 1) / 2 + (diameter2 + 1) / 2 + 1;
return Math.Max(Math.Max(diameter1, diameter2), crossDiameter);
}
}
var minimumDiameterAfterMerge = function(edges1, edges2) {
function buildGraph(edges) {
const graph = new Map();
for (const [u, v] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u).push(v);
graph.get(v).push(u);
}
return graph;
}
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
const distances = new Map();
distances.set(start, 0);
let farthest = start;
let maxDist = 0;
while (queue.length > 0) {
const node = queue.shift();
const neighbors = graph.get(node) || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
const newDist = distances.get(node) + 1;
distances.set(neighbor, newDist);
queue.push(neighbor);
if (newDist > maxDist) {
maxDist = newDist;
farthest = neighbor;
}
}
}
}
return { node: farthest, distance: maxDist };
}
function getDiameter(edges) {
if (edges.length === 0) return 0;
const graph = buildGraph(edges);
const nodes = Array.from(graph.keys());
const first = bfs(graph, nodes[0]);
const second = bfs(graph, first.node);
return second.distance;
}
const diameter1 = getDiameter(edges1);
const diameter2 = getDiameter(edges2);
const radius1 = Math.ceil(diameter1 / 2);
const radius2 = Math.ceil(diameter2 / 2);
return Math.max(diameter1, diameter2, radius1 + radius2 + 1);
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n + m) | 需要对两棵树各进行两次BFS遍历来计算直径，每次BFS的时间复杂度为O(节点数) |
| 空间复杂度 | O(n + m) | 构建图的邻接表和BFS队列所需的空间 |