题目
给你一个无向无环图，这个图的任何一个节点都可以当成一个树的根节点。让你找到形成的树的高度最小的那几个根节点。
首先，这个根节点要么只有1个，要么只有2个。 而且就在图中最长的一条路径上，如果这个路径上的节点数为偶数，那就是2个，否则就是1个
那么怎么找这条最长路径呢？首先从任意 一个点出发，找到离它最远的点t1,然后从t1出发找到离它最远的点t2,t1和t2就是最长的路径上的两个端点
代码语言：javascript复制class Solution {
public:
vector<int> edge[100005];
int vis[100005];
int t1, t2;
int d1, d2;
int path[100005];
int pos;
int ans1, ans2;
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<int> ans;
if (edges.size() == 0)
return ans;
for(int i=0;i<n;i )
{
v.push_back(edge);
}
for (int i = 0; i < edges.size(); i )
{
edge[edges[i][0]].push_back(edges[i][1]);
edge[edges[i][1]].push_back(edges[i][0]);
}
ans2 = -1;
pos = 0;
d1 = d2 = 0;
memset(vis,0,sizeof(vis));
vis[0]=1;
DFS(0, 1);
path[pos ] = t1;
memset(vis,0,sizeof(vis));
vis[t1]=1;
DFS2(t1, 1);
ans.push_back(ans1);
if (ans2 != -1)
ans.push_back(ans2);
return ans;
}
void DFS(int node,int deep)
{
if (d1 < deep)
{
d1 = deep;
t1 = node;
}
for (int i = 0; i < edge[node].size(); i )
{
if(vis[edge[node][i]])
continue;
vis[edge[node][i]]=1;
DFS(edge[node][i], deep 1);
}
}
void DFS2(int node, int deep)
{
if (d2 < deep)
{
if (pos & 1)
{
ans1 = path[pos / 2];
ans2 = -1;
}
else
{
ans2 = path[pos / 2];
ans1 = path[pos / 2 - 1];
}
d2 = deep;
}
for (int i = 0; i < edge[node].size(); i )
{
if(vis[edge[node][i]])
continue;
vis[edge[node][i]]=1;
path[pos ] = edge[node][i];
DFS2(edge[node][i], deep 1);
pos--;
}
}
};
