For an 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 :
Input:n = 4,edges = [[1, 0], [1, 2], [1, 3]]0 | 1 / \ 2 3 Output:[1]
Example 2 :
Input:n = 6,edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]0 1 2 \ | / 3 | 4 | 5 Output:[3, 4]
Note:
- According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
- The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Related Topics:
Breadth-first Search, Graph
Similar Questions:
Find the leaf nodes, trim them from the graph. Repeat this process until the graph only has 1 or 2 nodes left.
// OJ: https://leetcode.com/problems/minimum-height-trees
// Author: github.com/lzl124631x
// Time: O(V + E)
// Space: O(V + E)
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& E) {
if (n == 1) return { 0 };
vector<int> indegree(n), ans;
vector<vector<int>> G(n);
for (auto &e : E) {
int u = e[0], v = e[1];
indegree[u]++;
indegree[v]++;
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 1) q.push(i);
}
while (n > 2) {
int cnt = q.size();
while (cnt--) {
int u = q.front();
q.pop();
--n;
for (int v : G[u]) {
if (--indegree[v] == 1) q.push(v);
}
}
}
while (q.size()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};