拓扑排序变种题：Leetcode310最小高度树

问题：

思路：

借用了BFS的思想，一次性将度为1的节点全部删除，不断进行此操作，直至只剩2个或1个节点

正确性证明：
无向无环图A在删除度为1的结点后得到无向无环图B。可以证明，图A所成最小高度树TreeA是由图B所成的最小高度树TreeB接上被删除结点后构成的。反证法：图B所成的树TreeB如果不是最小高度树，那么存在图B的最小高度树TreeB’，TreeB’的高度比TreeB更小。那么TreeB’接上被删除结点后高度比TreeA更小，这与TreeA是最小高度树矛盾。

既然图A的最小高度树是由图B的最小高度树接上被删除的结点所成。那么图A的最小高度树的根结点与图B的最小高度树的根结点是相同的，因为，接上被删除的结点不会成为根结点，否则相比不成为根结点的高度还要高1。因此找图A的最小高度树的根结点演变为找图B的最小高度树的根结点。

使用队列，首先将度为1的节点全部入队，计算队列长度
之后进入循环，循环的终止条件为剩下的节点数<=2。
在循环中先将节点数减去队列长度得到剩余节点数，接下来每次将队列中元素pop出，并将已pop出的元素的度赋为0（该节点已被删除），对于该元素邻接表中的所有未被删除的元素（度不为0），将其度-1，若减1后度为1，将其加入队列

代码：

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> ans;
        if( n==1 )
        {
            ans.push_back(0);
            return ans;
        }
        if( n==2 )
        {
            ans.push_back(0);
            ans.push_back(1);
            return ans;
        }
        int* indegree;
        indegree=(int*)malloc( n*sizeof(int) );
        int i;
        for( i=0;i<n;i++ )
            indegree[i]=0;
        for( i=0;i<edges.size();i++ )
        {
            indegree[ edges[i][0] ]++;
            indegree[ edges[i][1] ]++;
        }
        vector<vector<int>> table;
        for( i=0;i<n;i++ )
            table.push_back( vector<int>() );
        for( i=0;i<edges.size();i++ )
        {
            table[ edges[i][1] ].push_back( edges[i][0] );
             table[ edges[i][0] ].push_back( edges[i][1] );
        }
        queue<int> queue;
        for( i=0;i<n;i++ )
        {
            if( indegree[i]==1 )
            {
                queue.push(i);
            }
        }
        int len=queue.size();
        int vertex;
        while( n>2 )
        {   
            n-=len;
            while( len-- )
            {
                vertex=queue.front();
                queue.pop();
                indegree[vertex]=0;
                for( i=0;i<table[vertex].size();i++ )
                {   
                    if( indegree[ table[vertex][i] ]!=0 ) 
                    {   
                        if( --indegree[ table[vertex][i] ]==1 )
                            queue.push( table[vertex][i] ); 
                    }   
                }
            }
            len=queue.size();
        }
        while( queue.size()!=0 )
        {
            vertex=queue.front();
            queue.pop();
            ans.push_back(vertex);
        }
        return ans;
    }
};