Dare2Solve
You are given an undirected graph represented by n
nodes, where n
is the number of nodes. The edges of the graph are given in a 2D list edges
, where each element is a pair [a, b]
representing an edge between nodes a
and b
. The task is to find all possible root nodes of the Minimum Height Trees (MHTs) that can be formed. A tree's height is defined as the number of edges on the longest path from the root to any leaf. A Minimum Height Tree (MHT) has the smallest possible height among all trees formed from the graph.
The problem can be understood as finding the "center" of the graph, which is the optimal root(s) for the MHT.
n == 1
), the answer is simply [0]
.class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
unordered_map<int, vector<int>> adj;
for (int i = 0; i < n; i++) {
adj[i] = vector<int>();
}
// Populate adjacency list
for (const auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
unordered_map<int, int> edgeCount;
queue<int> leaves;
for (auto& [src, neighbors] : adj) {
if (neighbors.size() == 1) {
leaves.push(src);
}
edgeCount[src] = neighbors.size();
}
// Reduce the graph iteratively
while (!leaves.empty()) {
if (n <= 2) {
vector<int> result;
while (!leaves.empty()) {
result.push_back(leaves.front());
leaves.pop();
}
return result;
}
int len = leaves.size();
for (int i = 0; i < len; i++) {
int node = leaves.front();
leaves.pop();
n--;
for (int nei : adj[node]) {
edgeCount[nei]--;
if (edgeCount[nei] == 1) {
leaves.push(nei);
}
}
}
}
return {};
}
};
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
adj = defaultdict(list)
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
edge_count = {}
leaves = deque()
for src, neighbors in adj.items():
if len(neighbors) == 1:
leaves.append(src)
edge_count[src] = len(neighbors)
# Reduce the graph iteratively
while leaves:
if n <= 2:
return list(leaves)
len_leaves = len(leaves)
for _ in range(len_leaves):
node = leaves.popleft()
n -= 1
for nei in adj[node]:
edge_count[nei] -= 1
if edge_count[nei] == 1:
leaves.append(nei)
return []
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Arrays.asList(0);
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int i = 0; i < n; i++) {
adj.put(i, new ArrayList<>());
}
// Populate adjacency list
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
Map<Integer, Integer> edgeCount = new HashMap<>();
Queue<Integer> leaves = new LinkedList<>();
for (Map.Entry<Integer, List<Integer>> entry : adj.entrySet()) {
int src = entry.getKey();
List<Integer> neighbors = entry.getValue();
if (neighbors.size() == 1) {
leaves.offer(src);
}
edgeCount.put(src, neighbors.size());
}
// Reduce the graph iteratively
while (!leaves.isEmpty()) {
if (n <= 2) {
return new ArrayList<>(leaves);
}
int len = leaves.size();
for (int i = 0; i < len; i++) {
int node = leaves.poll();
n--;
for (int nei : adj.get(node)) {
edgeCount.put(nei, edgeCount.get(nei) - 1);
if (edgeCount.get(nei) == 1) {
leaves.offer(nei);
}
}
}
}
return new ArrayList<>();
}
}
/**
* @param {number} n
* @param {number[][]} edges
* @return {number[]}
*/
var findMinHeightTrees = function(n, edges) {
if (n === 1 || !edges) return [0]
const adj = {}
for (let i = 0; i < n; i ++) {
adj[i] = []
}
//populate map
for (let [n1,n2] of edges) {
if (adj[n1]) adj[n1].push(n2)
if (adj[n1]) adj[n2].push(n1)
}
const edgeCount = {}
let leaves = [] // queue
for (let [src, neighbor] of Object.entries(adj)) {
if (neighbor.length === 1) {
leaves.push(src)
}
edgeCount[src] = neighbor.length
}
// build graph with queue
while (leaves.length) {
if ( n <= 2){
return leaves
}
let len = leaves.length
for (let i = 0; i < len; i++) {
let node = leaves.shift()
console.log(node)
n -=1
for (let nei of adj[node]) {
edgeCount[nei] -=1
if (edgeCount[nei] === 1) {
leaves.push(nei)
}
}
}
}
};