🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires connecting two trees such that the resulting tree has the minimum possible diameter. The diameter of a tree is defined as the longest path between any two nodes in the tree. To minimize the diameter after connecting two trees, we need to strategically choose nodes from each tree to connect.
Approach
- Calculate Tree Diameters: First, compute the diameters of both trees: - Use Depth-First Search (DFS) to find the diameter of each tree. Start from an arbitrary node (often node 0 for simplicity).
- Connecting Trees: After obtaining the diameters (
d1
for the first tree andd2
for the second tree), the possible diameters of the resulting tree are: -d1 + d2 + 1
: This accounts for the worst-case scenario where the longest path in the resulting tree goes through the connecting edge. - Choose Connecting Nodes: To achieve the minimum diameter, connect nodes that minimize the impact on the existing diameters. A strategic choice is often connecting the centroid or a node close to the centroid of each tree.
- Compute Minimum Diameter: Calculate the possible diameters resulting from connecting different pairs of nodes from both trees and choose the minimum diameter.
- Implementation Details: Implement DFS to calculate tree diameters and carefully choose nodes for connection to minimize the resulting diameter. Edge cases include trees with minimal nodes (like single-node trees).
Complexity
- Time Complexity: - Calculating tree diameters using DFS: \( O(n) \) for the first tree and \( O(m) \) for the second tree, where \( n \) and \( m \) are the number of nodes in each tree. - Overall, the time complexity is \( O(n + m) \).
- Space Complexity: - Additional space for storing adjacency lists and recursive call stack during DFS: \( O(n + m) \).
This approach ensures that we find the optimal way to connect the two trees while minimizing the diameter of the resulting tree efficiently.
Code Explanation
var minimumDiameterAfterMerge = function (edges1, edges2) {
- Defines a function
minimumDiameterAfterMerge
that takes two arguments,edges1
andedges2
.
var getDiameter = (edges) => {
- Defines an inner function
getDiameter
that calculates the diameter of a tree given its edges.
let map = Array(edges.length + 1)
.fill()
.map(() => []);
- Creates an adjacency list
map
to represent the graph. It initializes an array of empty arrays.
for (let [i, j] of edges) {
map[i].push(j);
map[j].push(i);
}
- Fills the adjacency list by iterating over each edge
[i, j]
and addingj
to the list of neighbors ofi
and vice versa.
let res = 0;
- Initializes a variable
res
to store the maximum diameter found.
var dfs = (node, parent) => {
let maxDepth = 1;
- Defines a depth-first search (DFS) function
dfs
that calculates the depth of the tree and updates the diameter. It initializesmaxDepth
to 1.
for (let neighbor of map[node]) {
if (neighbor === parent) continue;
let depth = dfs(neighbor, node);
res = Math.max(res, maxDepth + depth);
maxDepth = Math.max(maxDepth, 1 + depth);
}
return maxDepth;
};
- Iterates over the neighbors of the current
node
. If the neighbor is theparent
, it continues to the next iteration. It calculates thedepth
by recursively callingdfs
on the neighbor. Updatesres
with the maximum diameter found so far. UpdatesmaxDepth
with the maximum depth found so far. ReturnsmaxDepth
.
dfs(0, -1);
- Calls the
dfs
function starting from node0
with-1
as the parent.
return res;
};
- Returns the diameter of the tree.
let d1 = getDiameter(edges1);
let d2 = getDiameter(edges2);
- Calculates the diameters of the two trees,
d1
andd2
.
return Math.max(d1 - 1, d2 - 1, Math.floor(d1 / 2) + Math.floor(d2 / 2) + 1);
};
- Returns the maximum diameter after merging the two trees. The formula calculates the possible maximum diameter by considering the largest tree and the sum of half-diameters of both trees plus one.
Code
C++
class Solution {
public:
int minimumDiameterAfterMerge(vector>& edges1, vector>& edges2) {
int d1 = getDiameter(edges1);
int d2 = getDiameter(edges2);
return max(max(d1 - 1, d2 - 1), d1 / 2 + d2 / 2 + 1);
}
private:
int getDiameter(vector>& edges) {
unordered_map> map;
for (auto& edge : edges) {
int i = edge[0];
int j = edge[1];
map[i].push_back(j);
map[j].push_back(i);
}
int res = 0;
dfs(0, -1, map, res);
return res;
}
int dfs(int node, int parent, unordered_map>& map, int& res) {
int maxDepth = 1;
for (int neighbor : map[node]) {
if (neighbor == parent)
continue;
int depth = dfs(neighbor, node, map, res);
res = max(res, maxDepth + depth);
maxDepth = max(maxDepth, 1 + depth);
}
return maxDepth;
}
};
Python
class Solution:
def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
def getDiameter(edges):
map = defaultdict(list)
for i, j in edges:
map[i].append(j)
map[j].append(i)
res = [0]
def dfs(node, parent):
maxDepth = 1
for neighbor in map[node]:
if neighbor == parent:
continue
depth = dfs(neighbor, node)
res[0] = max(res[0], maxDepth + depth)
maxDepth = max(maxDepth, 1 + depth)
return maxDepth
dfs(0, -1)
return res[0]
d1 = getDiameter(edges1)
d2 = getDiameter(edges2)
return max(d1 - 1, d2 - 1, d1 // 2 + d2 // 2 + 1)
Java
class Solution {
public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
int d1 = getDiameter(edges1);
int d2 = getDiameter(edges2);
return Math.max(Math.max(d1 - 1, d2 - 1), d1 / 2 + d2 / 2 + 1);
}
private int getDiameter(int[][] edges) {
List> map = new ArrayList<>();
for (int i = 0; i < edges.length + 1; i++) {
map.add(new ArrayList<>());
}
for (int[] edge : edges) {
int i = edge[0];
int j = edge[1];
map.get(i).add(j);
map.get(j).add(i);
}
int[] res = { 0 };
dfs(0, -1, map, res);
return res[0];
}
private int dfs(int node, int parent, List> map, int[] res) {
int maxDepth = 1;
for (int neighbor : map.get(node)) {
if (neighbor == parent)
continue;
int depth = dfs(neighbor, node, map, res);
res[0] = Math.max(res[0], maxDepth + depth);
maxDepth = Math.max(maxDepth, 1 + depth);
}
return maxDepth;
}
}
JavaScript
/**
* @param {number[][]} edges1
* @param {number[][]} edges2
* @return {number}
*/
var minimumDiameterAfterMerge = function (edges1, edges2) {
var getDiameter = (edges) => {
let map = Array(edges.length + 1).fill().map(() => []);
for (let [i, j] of edges) {
map[i].push(j);
map[j].push(i);
}
let res = 0;
var dfs = (node, parent) => {
let maxDepth = 1;
for (let neighbor of map[node]) {
if (neighbor === parent) continue;
let depth = dfs(neighbor, node);
res = Math.max(res, maxDepth + depth);
maxDepth = Math.max(maxDepth, 1 + depth);
}
return maxDepth;
};
dfs(0, -1);
return res;
};
let d1 = getDiameter(edges1);
let d2 = getDiameter(edges2);
return Math.max(d1 - 1, d2 - 1, Math.floor(d1 / 2) + Math.floor(d2 / 2) + 1);
};