Sponsored
Sponsored
This approach uses an iterative method to trim the leaf nodes layer by layer until you are left with the centermost nodes, which are the roots of the Minimum Height Trees.
The idea is similar to peeling layers of an onion from the outside to the inside. The process stops when there are no more than two nodes left.
Time Complexity: O(n), since each node and edge is processed once.
Space Complexity: O(n), for storing edges and nodes’ degrees.
1#include <vector>
2#include <queue>
3using namespace std;
4
5vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
6 if (n == 1) return {0};
7
8 vector<int> degree(n, 0);
9 vector<vector<int>> adj(n);
10
11 for (const auto& edge : edges) {
12 adj[edge[0]].push_back(edge[1]);
13 adj[edge[1]].push_back(edge[0]);
14 degree[edge[0]]++;
15 degree[edge[1]]++;
16 }
17
18 queue<int> leaves;
19 for (int i = 0; i < n; i++) {
20 if (degree[i] == 1) leaves.push(i);
21 }
22
23 int count = n;
24 while (count > 2) {
25 int size = leaves.size();
26 count -= size;
27
28 for (int i = 0; i < size; i++) {
29 int leaf = leaves.front();
30 leaves.pop();
31 degree[leaf]--;
32
33 for (int neighbor : adj[leaf]) {
34 if (--degree[neighbor] == 1) {
35 leaves.push(neighbor);
36 }
37 }
38 }
39 }
40
41 vector<int> result;
42 while (!leaves.empty()) {
43 result.push_back(leaves.front());
44 leaves.pop();
45 }
46
47 return result;
48}
49The C++ code uses a queue to iteratively remove leaves, reducing the graph till potential centroids are found. It leverages vectors for adjacency list creation and manages the node degree.
This technique applies two breadth-first searches (BFS). Start from any node, find the farthest node to determine a tree diameter. From this end node, perform another BFS to determine the second endpoint. The center of the path between these endpoints, which are the potential MHT roots, is found.
Time Complexity: O(n), for initializing and iterating over nodes.
Space Complexity: O(n), due to graph adjacency representations and queue processing.
1import java.util.*;
2
3
In the Java solution, adjacency sets represent connections with degree checks for leaves. The while loop prunes tree leaves iteratively until potential centroids, interpreted as MHTs, are left.