题目说明给定两棵无向树的边数组 edges1 和 edges2 分别从两棵树中选一个节点连一条边合并为一棵新树求合并后新树的最小可能直径。树的直径定义为树中任意两节点之间的最长路径长度。核心思路要让合并后的直径最小最优方式是将两棵树各自的**直径中点树中心**相连。合并后的最终直径由三者最大值决定1. 第一棵树自身直径 d12. 第二棵树自身直径 d23. 跨树最长路径两树半径之和 1连接边其中树的半径 ⌈d/2⌉ (d1)/2最终公式 max(d1, d2, (d11)/2 (d21)/2 1)树直径求解两次BFS1. 从任意节点出发BFS找到距离最远的节点 u2. 从 u 出发再次BFS找到最远节点 v3. u 到 v 的路径长度即为树的直径Java 完整实现javaimport java.util.*;class Solution {public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {int d1 getTreeDiameter(edges1);int d2 getTreeDiameter(edges2);int radius1 (d1 1) / 2;int radius2 (d2 1) / 2;return Math.max(Math.max(d1, d2), radius1 radius2 1);}// 计算无向树的直径private int getTreeDiameter(int[][] edges) {int n edges.length 1;ListInteger[] adj new List[n];for (int i 0; i n; i) {adj[i] new ArrayList();}for (int[] e : edges) {adj[e[0]].add(e[1]);adj[e[1]].add(e[0]);}// 两次BFS求直径int[] first bfs(adj, 0);int[] second bfs(adj, first[0]);return second[1];}// BFS返回值[最远节点编号, 到起点的最远距离]private int[] bfs(ListInteger[] adj, int start) {int n adj.length;int[] dist new int[n];Arrays.fill(dist, -1);QueueInteger queue new LinkedList();queue.offer(start);dist[start] 0;int farNode start;int maxDist 0;while (!queue.isEmpty()) {int u queue.poll();for (int v : adj[u]) {if (dist[v] -1) {dist[v] dist[u] 1;if (dist[v] maxDist) {maxDist dist[v];farNode v;}queue.offer(v);}}}return new int[]{farNode, maxDist};}}复杂度分析- 时间复杂度O(n m)n、m 分别为两棵树的节点数。每棵树执行两次线性BFS。- 空间复杂度O(n m)存储邻接表与BFS距离数组。正确性说明连接中心点最优的核心原因- 跨树最长路径 树A内点到连接点的最远距离 1 树B内点到连接点的最远距离- 选择直径中点作为连接点时该点到树内所有节点的最大距离即半径最小- 因此跨树最长路径的最小值就是两树半径之和 1需要我补充DFS版本的直径实现或者添加边界测试用例吗