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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_NODES 20000
6
7int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize){
8 if (n == 1) {
9 *returnSize = 1;
10 int* res = (int*)malloc(sizeof(int));
11 res[0] = 0;
12 return res;
13 }
14
15 int* degrees = (int*)calloc(n, sizeof(int));
16 int* adj[MAX_NODES];
17 for (int i = 0; i < n; ++i) adj[i] = (int*)malloc(sizeof(int) * n);
18 int adjLen[MAX_NODES] = {0};
19
20 for (int i = 0; i < edgesSize; ++i) {
21 int u = edges[i][0], v = edges[i][1];
22 adj[u][adjLen[u]++] = v;
23 adj[v][adjLen[v]++] = u;
24 degrees[u]++;
25 degrees[v]++;
26 }
27
28 int queue[MAX_NODES];
29 int front = 0, rear = 0;
30 for (int i = 0; i < n; ++i) {
31 if (degrees[i] == 1) {
32 queue[rear++] = i;
33 }
34 }
35
36 int count = n;
37 while (count > 2) {
38 int size = rear - front;
39 count -= size;
40 for (int i = 0; i < size; ++i) {
41 int leaf = queue[front++];
42 degrees[leaf]--;
43 for (int j = 0; j < adjLen[leaf]; ++j) {
44 int neighbor = adj[leaf][j];
45 if (--degrees[neighbor] == 1) {
46 queue[rear++] = neighbor;
47 }
48 }
49 }
50 }
51
52 *returnSize = rear - front;
53 int* res = (int*)malloc((*returnSize) * sizeof(int));
54 for (int i = 0; front < rear; ++front, ++i) {
55 res[i] = queue[front];
56 }
57
58 free(degrees);
59 for (int i = 0; i < n; ++i) free(adj[i]);
60
61 return res;
62}
63The C solution describes trimming nodes from the outermost layer (leaves), updating degrees, and reducing the graph until finding potential centroids. This is implemented using arrays to keep track of each node's neighbors and queue for processing leaves.
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.
1from collections import defaultdict, deque
2
3def
This Python implementation uses adjacency sets and deque to handle the leaf removal process, eventually finding the MHT roots.