How do I choose which nodes to connect in Find Minimum Diameter After Merging Two Trees?

Pick nodes near the endpoints of each tree's diameter; connecting shallow nodes rarely reduces the maximum path length.

Can this method handle large trees efficiently?

Yes, using BFS or DFS ensures O(n + m) time complexity, which scales linearly with the number of nodes.

Why is it necessary to compute each tree's diameter first?

Knowing each tree's diameter helps determine the minimum possible combined diameter and identifies optimal nodes to connect.

Does the connecting edge always increase the diameter by one?

Not necessarily; the increase depends on which nodes are connected and how the diameters of the original trees interact.

Is BFS better than DFS for this problem?

Either works for finding farthest nodes; BFS may be easier to implement iteratively, while DFS can use recursion.

#3203

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

合并两棵树后的最小直径

给你两棵无向树，分别有 n 和 m 个节点，节点编号分别为 0 到 n - 1 和 0 到 m - 1 。给你两个二维整数数组 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [a i , b i ] 表示在第一棵树中节点 a i 和 b…

树深度优先搜索广度优先搜索图

题目描述

给你两棵无向树，分别有 n 和 m 个节点，节点编号分别为 0 到 n - 1 和 0 到 m - 1 。给你两个二维整数数组 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [a_i, b_i] 表示在第一棵树中节点 a_i 和 b_i 之间有一条边，edges2[i] = [u_i, v_i] 表示在第二棵树中节点 u_i 和 v_i 之间有一条边。

你必须在第一棵树和第二棵树中分别选一个节点，并用一条边连接它们。

请你返回添加边后得到的树中，最小直径 为多少。

一棵树的直径指的是树中任意两个节点之间的最长路径长度。

示例 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⁵
edges1.length == n - 1
edges2.length == m - 1
edges1[i].length == edges2[i].length == 2
edges1[i] = [a_i, b_i]
0 <= a_i, b_i < n
edges2[i] = [u_i, v_i]
0 <= u_i, v_i < m
输入保证 edges1 和 edges2 分别表示一棵合法的树。

lightbulb

解题思路

方法一：两次 DFS

我们记 $d_1$ 和 $d_2$ 分别为两棵树的直径，那么合并后的树的直径有以下两种情况：

合并后的树的直径为原始的一棵树的直径，即 $\max(d_1, d_2)$ ；
合并后的树的直径经过原始的两棵树。我们分别计算原始的两棵树的半径 $r_1 = \lceil \frac{d_1}{2} \rceil$ 和 $r_2 = \lceil \frac{d_2}{2} \rceil$ ，那么合并后的树的直径为 $r_1 + r_2 + 1$ 。

我们取这两种情况的最大值即可。

在计算树的直径时，我们可以使用两次 DFS。首先我们任选一点出发，找到距离该点最远的点，记为 $a$ 。然后从点 $a$ 出发，找到距离点 $a$ 最远的点，记为 $b$ 。可以证明，点 $a$ 和点 $b$ 之间的路径即为树的直径。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别为两棵树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def minimumDiameterAfterMerge(
        self, edges1: List[List[int]], edges2: List[List[int]]
    ) -> int:
        d1 = self.treeDiameter(edges1)
        d2 = self.treeDiameter(edges2)
        return max(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1)

    def treeDiameter(self, edges: List[List[int]]) -> int:
        def dfs(i: int, fa: int, t: int):
            for j in g[i]:
                if j != fa:
                    dfs(j, i, t + 1)
            nonlocal ans, a
            if ans < t:
                ans = t
                a = i

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        ans = a = 0
        dfs(0, -1, 0)
        dfs(a, -1, 0)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m) because BFS or DFS traverses each node once in both trees. Space complexity is O(n + m) to store adjacency lists for each tree and recursive or queue storage during traversal.
空间	O(n + m)

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to quickly identify diameter endpoints using BFS or DFS.
question_mark
Watch for reasoning on how connecting nodes affects the combined tree's diameter.
question_mark
Notice whether candidates correctly optimize the maximum path rather than connecting arbitrarily.

warning

常见陷阱

外企场景

error
Choosing arbitrary nodes instead of endpoints can lead to non-minimal diameters.
error
Neglecting the internal diameter of each tree before merging can miscalculate the final result.
error
Forgetting to consider the longest path that passes through the connecting edge may produce incorrect outputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum diameter when merging more than two trees sequentially.
arrow_right_alt
Find the maximum diameter instead of minimum after connecting trees.
arrow_right_alt
Apply the same logic to weighted trees where edges have lengths other than 1.

help

常见问题

外企场景

继续练习

#2477 到达首都的最少油耗 #2467 树上最大得分和路径 #2368 受限条件下可到达节点的数目