leetcode 310. Minimum Height Trees

The title is to give a picture , Please lift a node , The height of the formed tree is the smallest .

The first idea is violent search .

         Raise every point , Then calculate and compare the height of the tree .

         The result is timeout .

         Optimized some , It is found that there is still no way to deal with it within the specified time .

I saw the great God on the Internet huifeng guan And the solution before the cruel problem group , I feel too low 了 .

Since the topic requires that the height of the tree after lifting a node is the smallest , Under the problem transformation, the distance from a certain node to each other node is the shortest .

The layout of my high school building is similar to that of this problem , The building of grade one in North America , high , Senior 3 laboratory building , Teacher building , music , Gymnasium . They are all linked by stairs .

Our problem is like arranging the office of the high school teaching director , To find a suitable position . This can quickly reach the battlefield .

Then the problem is simpler , Arrange the office of the director of education to the most central building in all buildings .

The first example shows , Arrange the teaching director in 1 You can reach the battlefield at the first time .

For the second example

If you want to find the core position, you have to peel onions , Peel layer by layer .

First peel off the outermost layer of onion （ floor ）, That is to say 5, 0, 1, 2 These outermost onions （ floor ）, Then it's left 3,4.

There is no way to peel these two buildings , Even the existence of the teaching director can be eliminated .

In this case , Arrange the teaching director to 3 perhaps 4 Building No .

Use topological sorting to peel from the outside , Peel to the last layer . What remains is the answer .

 class Solution {
public:
    unordered_map<int ,vector<int>> buildGraphic(vector<vector<int>>& edges)
    {
        unordered_map<int ,vector<int>> neighbors;
        
        for(auto edge: edges) 
        {
            neighbors[edge[0]].push_back(edge[1]);
            neighbors[edge[1]].push_back(edge[0]);
        }
                
        return neighbors;
    }
    
    unordered_map<int, int> buildDegree(unordered_map<int ,vector<int>> neighbors){
        unordered_map<int, int> degree;
        
        for(auto neighbor: neighbors){
            degree[neighbor.first] = neighbor.second.size();
        }
        
        return degree;
    }
    
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        //build graphic
        //set every node as root node and using bfs go through the tree level by level.
        //push the root if the levels is min.
        vector<int> ret;
        if(edges.size() ==0 && n !=0)
            for(int i=0;i<n;i++)
                ret.push_back(i);
        
        unordered_map<int ,vector<int>> neighbors = buildGraphic(edges);
        unordered_map<int, int> degrees = buildDegree(neighbors);
        unordered_set<int> accessed;
        
        queue<int> myqueue;
        //push the most out building into the queue
        for(auto degree: degrees) {
            if(degree.second == 1)
                myqueue.push(degree.first);
        }
        
        while(!myqueue.empty()) {
            ret.clear();
            int size = myqueue.size();
            for(int i=0;i<size;i++) {
                int cur=myqueue.front();
                myqueue.pop();
                ret.push_back(cur);
                
                for(auto neighbor: neighbors[cur]){
                    degrees[neighbor]--;
                    if(degrees[neighbor] == 1)
                        myqueue.push(neighbor);
                }
            }
        }
        return ret;
    }
};