最小高度树

变量简洁正确完整思路
拓扑排序，删除前的图A是，删除入度为1的节点后的图B，A的最小生成树是B的最小生成树叶子接上删除的节点，
无向图拓扑排序，入度至少为1，初始化graph需要edges[i][0]  edges[i][1]都初始化为彼此，都要更新入度，topoSort把入度1都放入que，然后一次性删除掉que原来入度1的元素也就是叶子元素（indegrees[cur]=0表示cur删除），对邻接的indegrees[graph[cur][i]]大于1的
--如果是1就把graph[cur][i]放到que，这样
[image:1628663260701.png]
每次while(cnt--)可以删除掉所有叶子节点，用cnt表示此次需要删除的叶子节点
[image:1628663584807.png]
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1)return {0};
        if(n==2)return {0,1};
        indegrees.resize(n);
        graph.resize(n);
        for(int i=0;i<edges.size();i++){
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
            indegrees[edges[i][0]]++;
            indegrees[edges[i][1]]++;
        }
        return topoSort(n);
    }
private:
    vector<int>topoSort(int n){
        queue<int>que;
        for(int i=0;i<n;i++)if(indegrees[i]==1)que.push(i);
        int cnt=que.size();
        while(n>2){
            n-=cnt;
            while(cnt--){
                int cur=que.front();que.pop();
                indegrees[cur]=0;
                for(int i=0;i<graph[cur].size();i++){
                    if(indegrees[graph[cur][i]]>1){
                        indegrees[graph[cur][i]]--;
                        if(indegrees[graph[cur][i]]==1)que.push(graph[cur][i]);
                    }
                }
            }
            cnt=que.size();
        }
        vector<int>ans;
        while(!que.empty()){
            ans.push_back(que.front());
            que.pop();
        }
        return ans;
    }
    vector<vector<int>>graph;
    vector<int>indegrees;
};