LeetCode 310. 最小高度树

朴素bfs超时的解决方法。，当节点个数在5000及以上时，普通bfs超时。

此时采用类似拓扑排序的方法，每次将度为1的节点抹掉。最后一次才被抹掉的就是可能的节点。

class Solution {
public:
    vector findMinHeightTrees(int n, vector>& edges) {
        if (n == 1) return {0};
        vector ans;        
        unordered_map degree;
        vectorv[n];
        for(auto i:edges){
            degree[i[0]]++;
            degree[i[1]]++;
            v[i[0]].push_back(i[1]);
            v[i[1]].push_back(i[0]);
        }
        queue q;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) 
            q.push(i);
        }
        while (!q.empty()) {
            ans.clear();
            int size = q.size();
            while (size--) {		
            	//这个while什么意思？能不能写!q.empty()?
            	//不能，这个while是为了把 当层 节点全部抹掉而不动其他节点，注意不是所有节点，而是当层节点。
            	// 因为下面会不断push，意思是q里面是不断增加的，所以这个size来判断是不是当前层的，size==0说剩下的节点是下一层的
            	//同时这层不能不写，因为这是指导ans数组更新的条件。
                int cur = q.front();
                q.pop();
                ans.push_back(cur);
                degree[cur]--;
                for (auto i : v[cur]) {
                    degree[i]--;
                    if (degree[i] == 1) {
                        q.push(i);
                    }
                }
            }
        }     
        return ans;
    }
};