The basic idea

1 Find the longest path in the tree, start from node T1 to node T2; (first bfs find T1 and the second bfs find T2 also remember the parent path and number of nodes in the longest path. O(n))

2 Find the middle node/nodes from T2 to T1 (Get from parent path, need to take care of odd even cases, O(n))

I do not believe this is the best solution. And it takes 1000ms + to finished. Just for sharing!

```
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> res;
if (n==0) {
return res;
}
vector<vector<int>> G(n);
for (const pair<int,int> &edge: edges) {
G[edge.first].push_back(edge.second);
G[edge.second].push_back(edge.first);
}
queue<int> Q;
char *visited = new char[n];
memset(visited, 0, n*sizeof(char));
int cur = 0;
Q.push(0);
while (!Q.empty()) {
cur = Q.front();
Q.pop();
visited[cur] = true;
for (const int& next : G[cur]) {
if (!visited[next]) {
Q.push(next);
}
}
}
int T1 = cur;
Q.push(cur);
memset(visited, 0, n*sizeof(char));
int *parent = new int[n];
memset(parent, 0, n*sizeof(int));
int h = 0;
while (!Q.empty()) {
h++;
int size = Q.size();
for (int j = 0; j<size; ++j) {
cur = Q.front();
Q.pop();
visited[cur] = true;
for (const int& next : G[cur]) {
if (!visited[next]) {
parent[next] = cur;
Q.push(next);
}
}
}
}
int T2 = cur;
if (h&1) {
h/=2;
for (int i =0;i<h;++i) {
T2 = parent[T2];
}
res.push_back(T2);
} else {
h = h/2 -1;
for (int i =0;i<h;++i) {
T2 = parent[T2];
}
res.push_back(T2);
res.push_back(parent[T2]);
}
delete[] visited;
delete[] parent;
return res;
}
};
```