NeetCode #651LC-3203HardAdvanced Graphs
← Back to All Problems#651 · #3203 · Find Minimum Diameter After Merging Two Trees(合并两棵树后的最小直径)
📌 Problem Statement & Constraints
You are given two trees described by
edges1 and edges2. You must add exactly one edge connecting a node of the first tree to a node of the second. Return the minimum possible diameter of the resulting tree. Constraints: 1 <= number of nodes <= 10^5.💡 Core Algorithmic Approaches
- The diameter of the merged tree is the maximum of three quantities:
- ① the first tree's own diameter; ② the second tree's own diameter; ③
radius1 + radius2 + 1(the new edge plus the best attachment points). - The best attachment points are the centres, so the radius is
ceil(diameter / 2). - A tree's diameter is found with two BFS passes (the classic "farthest from any node, then farthest from that" trick).
💻 Benchmark Python3 Implementation
class Solution:
def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
from collections import defaultdict, deque
def diameter_and_radius(edges):
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
if not g:
return 0, 0 # a single node
def bfs(start):
dist = {start: 0}
q = deque([start])
far = start
while q:
node = q.popleft()
for nxt in g[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
q.append(nxt)
if dist[nxt] > dist[far]:
far = nxt
return far, dist[far]
a, _ = bfs(0) # farthest from an arbitrary node
b, d = bfs(a) # farthest from a -> the diameter
return d, (d + 1) // 2 # diameter, and the radius (ceil(d/2))
d1, r1 = diameter_and_radius(edges1)
d2, r2 = diameter_and_radius(edges2)
return max(d1, d2, r1 + r2 + 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + m): two BFS passes per tree.
💾 Space Complexity
O(n + m) for the adjacency lists.
⚠️ Interview Pitfalls & Follow-ups
- Attaching at arbitrary nodes: the centres minimise the resulting radius.
- Using
d // 2for the radius: the ceiling is required, hence(d + 1) // 2. - Forgetting to include both original diameters: the merged diameter is at least each of them.
- Handling a single-node tree: the diameter is 0 and the radius is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.