# LeetCode Minimum Height Trees

LeetCode 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   3
```

return `[1]`

Example 2:

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

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

return `[3, 4]`

Note:

(1) 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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

给定一个无向无环图，问以哪个顶点为根形成的有根树的树高是最小的，如果有多个这样的最小高度的有根树，则输出所有这样的根节点。

很有意思的一题，需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个，我想了想，应该最多只有两个吧。可以用反证法，假设有3个，则这3个根肯定会形成环，具体原因大家可以在纸上画个图举个例子就知道了。

然后我由题目的样例想到的是，把图转换为有根的最小高度的树，根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数，然后选两个度数最高的节点，对这两个点DFS求以他们为根时的树高，如果树高相同，说明这两个点都是答案，否则取树高更高的节点作为根节点。

但是很可惜，代码提交之后WA，错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。

```8     3
\    \
2----0----5----6----7----9
/    /
4    1```

在上图中，度数最多的前两个点是0和2，但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。

参考网上的题解，好巧妙呀。这种解法类似于剥洋葱，一层一层把叶子节点剥离掉，最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的，没剥掉一层，相当于树高减一，一直减，到最后还剩下的节点肯定就是根节点了。比如上图中，第一层剥掉8,3,9,4,1，变成下图

`2----0----5----6----8`

第二层剥掉之后变成下图

`0----5----6`

第三层剥掉之后就只剩下5号节点了，所以以5号节点为根，树的高度最低，只有3，而我的解法算出来的根节点0的树高是4，不是最小的。

`5`

剥洋葱的解法用BFS来实现就非常方便了，BFS天然就是一层循环就是剥掉一层。

代码中，初始时，我们把图转换为类似邻接表的结果，但是每个vector里存的是unordered_set，而不是list，因为剥洋葱的时候，比如第一层时剥掉8号节点时，我们同时需要把2号节点的邻接表中的8号节点删掉，所以用unordered_set.erase就非常方便。后面循环时，没剥一层，我们就检查一下，把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时，剩余的节点就是有根树的根节点。如果剩余两个节点，说明这两个节点的高度是一样的，都是正确答案。

代码如下：

```class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1)return{ 0 };
int m = edges.size();
vector<unordered_set<int>> graph(n, unordered_set<int>());
for (int i = 0; i < m; ++i) {
graph[edges[i].first].insert(edges[i].second);
graph[edges[i].second].insert(edges[i].first);
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (graph[i].size() == 1) q.push(i);
}
while (n > 2) {
int t = q.size();
n -= t;
while (t--) {
int leaf = q.front();
q.pop();
for (auto par : graph[leaf]) { // only one par
graph[par].erase(leaf);
if (graph[par].size() == 1)q.push(par);
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};
```

本代码提交AC，用时79MS。