?LeetCode刷題實戰(zhàn)310：最小高度樹
示例
解題
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
//處理特殊的情形
if(n==1){
return {0};
}
if(n==2){
return {0,1};
}
//建立圖
vector<vector<int>> graph(n);
//統(tǒng)計各個結(jié)點的入度，這里是無向圖，實際既相鄰的結(jié)點的數(shù)量
vector<int> in_degree(n,0);
for(vector<int>& edge:edges){
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
++in_degree[edge[0]];
++in_degree[edge[1]];
}
queue<int> q;//隊列實現(xiàn)廣度優(yōu)先搜索
//將起始的度為1的結(jié)點壓入到隊列中
for(int i=0;i<n;++i){
if(in_degree[i]==1){
q.push(i);
in_degree[i]=0;//標(biāo)識不再訪問，變相的刪除結(jié)點操作
}
}
//當(dāng)沒有遍歷的結(jié)點的數(shù)量小于等于2時，則終止循環(huán)，剩余的這1個或2個結(jié)點，即為中間結(jié)點
while(n>2){
int cur_size=q.size();//當(dāng)前層要刪除的結(jié)點數(shù)量
n-=cur_size;//刪除結(jié)點
//逐個遍歷要刪除的結(jié)點，減少相鄰的結(jié)點的度
while(cur_size--){
int cur_index=q.front();//當(dāng)前結(jié)點
q.pop();
//遍歷當(dāng)前結(jié)點的相鄰結(jié)點，再相鄰結(jié)點沒有被刪除過的情形下，既度符合要求的情形下
for(int& cur_i:graph[cur_index]){
if(in_degree[cur_i]>1){//度符合要求，則可以訪問
//該相鄰結(jié)點的度減1
--in_degree[cur_i];
//若度等于1，則說明也是新的葉子結(jié)點，既可以刪除的結(jié)點，壓入到隊列中，并將對應(yīng)的度置為0進(jìn)行標(biāo)識
if(in_degree[cur_i]==1){
q.push(cur_i);
in_degree[cur_i]=0;
}
}
}
}
}
//獲得結(jié)果
vector<int> res;
while(!q.empty()){
res.push_back(q.front());
q.pop();
}
return res;
}
};