第三天，写了好久，改了好几个版本终于过了
第一版： class Solution { public: vector findMinHeightTrees(int n, vector<vector>& edges) { vector du(n,0); vector v(n); vector<vector> graph(n,v); for(int i=0;i<edges.size();i++){ du[edges[i][0]]++; du[edges[i][1]]++; graph[edges[i][0]][edges[i][1]]++; graph[edges[i][1]][edges[i][0]]++; } int size=n; while(size>2){ for(int i=0;i<n;i++){ if(du[i]==0) continue; if(du[i]==1){ for(int j=0;j<n;j++){ if(graph[i][j]&&i!=j){ du[j]–; graph[i][j]=0; graph[j][i]=0; } } du[i]=0; size–; } } } vector re; for(int i=0;i<n;i++){ if(du[i]!=0) re.push_back(i); } return re;
}};
第二版： class Solution { public: vector findMinHeightTrees(int n, vector<vector>& edges) { vector du(n,0); vector v(n); vector<vector> graph(n,v); for(int i=0;i<edges.size();i++){ du[edges[i][0]]++; du[edges[i][1]]++; graph[edges[i][0]][edges[i][1]]++; graph[edges[i][1]][edges[i][0]]++; }
queue<int> del; for(int i=0;i<n;i++){ if(du[i]==1){ del.push(i); } } int size=n; while(!del.empty()){ int point=del.front(); del.pop(); du[point]=0; size--; cout<<point<<endl; cout<<"2:"<<du[2]<<endl; cout<<"3:"<<du[3]<<endl; for(int i=0;i<n;i++){ if(graph[i][point]&&i!=point){ graph[i][point]=0; graph[point][i]=0; du[i]--; } } for(int i=0;i<n;i++){ if(du[i]==0) continue; if(du[i]==1&&size>2){//想在这里判断，但是那样就会操作队列，使队列破坏 cout<<i<<endl; del.push(i); } } }
vector<int> re; for(int i=0;i<n;i++){ if(du[i]!=0) re.push_back(i); } return re; }};
第三版： class Solution { public: vector findMinHeightTrees(int n, vector<vector>& edges) { vector du(n,0); vector v(n); vector<vector> graph(n,v); for(int i=0;i<edges.size();i++){ du[edges[i][0]]++; du[edges[i][1]]++; graph[edges[i][0]][edges[i][1]]++; graph[edges[i][1]][edges[i][0]]++; } queue del;
for(int i=0;i<n;i++){ if(du[i]==1){ del.push(i); } } int size=n; while(!del.empty()){ int point=del.front(); del.pop(); du[point]=0; size--; //cout<<point<<endl; //cout<<"2:"<<du[2]<<endl; //cout<<"3:"<<du[3]<<endl; for(int i=0;i<n;i++){ if(graph[i][point]&&i!=point&&size>2){ graph[i][point]=0; graph[point][i]=0; du[i]--; if(du[i]==1&&size>2) del.push(i); } } } vector<int> re; for(int i=0;i<n;i++){ if(du[i]!=0) re.push_back(i); } return re; }};
终版：class Solution { public: vector findMinHeightTrees(int n, vector<vector>& edges) { if(n==1){ vector b; b.push_back(0); return b; } else if (n == 2) return{ 0,1 };
vector<int> du(n,0); vector<int> v; vector<vector<int>> graph(n,v);//图形表示，并初始化 for(int i=0;i<edges.size();i++){ du[edges[i][0]]++; du[edges[i][1]]++; graph[edges[i][0]].push_back(edges[i][1]); graph[edges[i][1]].push_back(edges[i][0]); } queue<int> del; for(int i=0;i<n;i++){ if(du[i]==1){ del.push(i); } } int c=del.size(); while(n>2){ n-=c; while(c--){ int point=del.front(); del.pop(); du[point]=0; //cout<<point<<endl; for(int i=0;i<graph[point].size();i++){ //cout<<i<<endl; //if(du[i]==0) continue; //cout<<i<<endl; if(du[graph[point][i]] != 0){ du[graph[point][i]]--; if (du[graph[point][i]] == 1) del.push(graph[point][i]); } } } c=del.size(); } vector<int> re; while(!del.empty()){ int d=del.front(); del.pop(); re.push_back(d); } return re; }};
