## Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format

The graph contains`n`

nodes which are labeled from`0`

to`n - 1`

. You will be given the number`n`

and a list of undirected`edges`

(each edge is a pair of labels).You can assume that no duplicate edges will appear in

`edges`

. Since all edges are undirected,`[0, 1]`

is the same as`[1, 0]`

and thus will not appear together in`edges`

.

Example 1:Given

`n = 4`

,`edges = [[1, 0], [1, 2], [1, 3]]`

0 | 1 / \ 2 3return

`[1]`

Example 2:Given

`n = 6`

,`edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]`

0 1 2 \ | / 3 | 4 | 5return

`[3, 4]`

Hint:

- How many MHTs can a graph have at most?

Note:(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by

exactlyone path. In other words, any connected graph without simple cycles is a tree.”(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Credits:

Special thanks to @dietpepsi for adding this problem and creating all test cases.Subscribe to see which companies asked this question

Show Similar Problems

class Solution { public: int MAX_INT = 0x7fffffff; unordered_map<int, unordered_map<int, int>> heights;// store heights given vertex and edge unordered_map<int, vector<int> >graph; vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { int height = MAX_INT; vector<int> res; // build graph graph.clear(); heights.clear(); for(auto it = edges.begin(); it != edges.end(); it++){ if(graph.find(it->first) == graph.end()){ graph[it->first] = vector<int>(); } if(graph.find(it->second) == graph.end()){ graph[it->second] = vector<int>(); } graph[it->first].push_back(it->second); graph[it->second].push_back(it->first); } // for each vertex in graph for(int i = 0; i < n; i++){ int localHeight = 0; for(auto it = graph[i].begin(); it != graph[i].end(); it++){ localHeight = max(localHeight, _MHT(i, *it)); } if(height == localHeight){ res.push_back(i); }else if(localHeight < height){ res.clear(); res.push_back(i); } height = min(localHeight, height); } return res; } //pv : previous vertex, v: current vertex int _MHT(int pv, int v){ int h = getHeight(pv, v); if(h >= 0){ return h; } else{ h = 0; for(auto it = graph[v].begin(); it != graph[v].end(); it++){ if(*it != pv){ h = max(_MHT(v, *it) + 1, h); } } setHeight(pv, v, h); return h; } } int getHeight(int pv, int v){ if(heights.find(pv) == heights.end() || heights[pv].find(v) == heights[pv].end()){ return -1; }else{ return heights[pv][v]; } } void setHeight(int pv, int v, int h){ if(heights.find(pv) == heights.end()){ heights[pv] = unordered_map<int, int>(); } heights[pv][v] = h; } };

### Topological sort like algorithm. O(V+E)

// Topological sort // O(V+E) class Solution { public: vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { unordered_map<int, unordered_set<int>> graph; vector<int> inDegree = vector<int>(n, 0); vector<int> res; // extreme case if(n == 1){ res.push_back(0); return res; } // build indegree vector for(auto it = edges.begin(); it != edges.end(); it++){ inDegree[it->first]++; inDegree[it->second]++; if(graph.find(it->first) == graph.end()){ graph[it->first] = unordered_set<int>(); } if(graph.find(it->second) == graph.end()){ graph[it->second] = unordered_set<int>(); } graph[it->first].insert(it->second); graph[it->second].insert(it->first); } // find all vetices with indegree 1 int restN = n; queue<int> readyQ, runningQ; for(int i = 0; i < n; i++){ if(inDegree[i] == 1){ readyQ.push(i); restN--; } } // finish, vertices in readyQ are the answer while(restN > 0){ runningQ = readyQ; // clear readyQ; readyQ = queue<int>(); while(!runningQ.empty()){ int v = runningQ.front(); runningQ.pop(); for(auto it = graph[v].begin(); it != graph[v].end(); it++){ if(--inDegree[*it] == 1){ readyQ.push(*it); restN--; } // remove edge graph[*it].erase(v); } } } while(!readyQ.empty()){ res.push_back(readyQ.front()); readyQ.pop(); } return res; } };

The performance is slightly improved by 20%.

Notes:

1. When there is a queue, use an unordered_set to mark the visited elements.

2. Use vector<unordered_set> to represent graph.

3. queue has push/pop/front member functions.

4. set has insert/erase/contains member functions.