本题给你一个无向图，其中有n个顶点，n-1条边，因此取其中的任意某顶点作为根，都可以构建成一棵树。那么本题的问题就是在这些树中找出高度最小的树，返回树的根节点；如果有多棵树的高度相同，则返回多个根节点。
思路1：一开始，我认为最直白的解法就是遍历所有的顶点，以该顶点为根，求此树的高度。最后找出高度最小的树就是答案。此为暴力法，但是暴力一般往往会超时，本题也不例外。所以就得另辟蹊径咯。
思路2：先找到所有的叶子节点(该顶点只与一个顶点连接，即只有一条边)，再删除所有的叶子节点，再继续找目前的叶子节点，再删除掉。直到找不到叶子节点为止。那么最后一次找到的叶子节点就是所求的根节点。这题算是trick吧，自己多画几个图，或许可以发现这个规律。
好了，代码如下。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<vector<int>>adj(n);
//构建邻接表
for (int i=0; i<edges.size(); ++i)
{
int x = edges[i].first;
int y = edges[i].second;
adj[x].push_back(y);
adj[y].push_back(x);
}
//处理边缘条件
vector<int>res;
if(edges.size() == 1)
{
res.push_back(edges[0].first);
res.push_back(edges[0].second);
return res;
}
if(edges.size() == 0)
return res;
//找叶子节点
for (int i=0; i<adj.size(); ++i)
{
if(adj[i].size() == 1)
res.push_back(i);
}
//删除叶子节点，再找叶子节点
while (1)
{
vector<int> next;//保存叶子节点
for (int i=0; i<res.size(); ++i)
{
int node = res[i];
//删除叶子节点
adj[adj[node][0]].erase(find(adj[adj[node][0]].begin(),adj[adj[node][0]].end(),node));
if(adj[adj[node][0]].size() == 1)
next.push_back(adj[node][0]);//添加叶子节点
}
if(next.empty())//找不到叶子节点
return res; //返回上一次找到的叶子节点
res = next;
}
}
};