思路：树形dp，d1[i]表示以i为根节点向下的最高高度,d2表以i为根节点的向下的次高高度，p1,p2记录节点高度，up[i]表示以i为根向上的最高高度
代码：
class Solution {
public:
vector> g;
vector p1,p2,d1,d2,up;
void dfs1(int u,int father){
for(int x:g[u]){
if(x==father) continue;
dfs1(x,u);
int d=d1[x]+1;
if(d>=d1[u]){
d2[u]=d1[u];d1[u]=d;
p2[u]=p1[u];p1[u]=x;
}else if(d>d2[u]){
d2[u]=d;
p2[u]=x;
}
}
}
void dfs2(int u,int father){
for(auto x:g[u]){
if(x==father) continue;
if(p1[u]==x) up[x]=max(up[u],d2[u])+1;
else up[x]=max(up[u],d1[u])+1;
dfs2(x,u);
}
}
vector findMinHeightTrees(int n, vector>& edges) {
g.resize(n);
d1=d2=p1=p2=up=vector(n);
for(auto &e:edges){
int a=e[0],b=e[1];
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(0,-1);
dfs2(0,-1);
int mind=n+1;
for(int i=0;i res;
for(int i=0;i
