My 88ms C++ TOPO-SORT solution with explanation,O(n+e) time and space.


  • 0
    H
    class Solution {
    public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<vector<int>> graph(n,vector<int>());
        vector<int> degree(n),ret;
        for(const auto & x:edges){/// build graph
            degree[x.first]++;degree[x.second]++;
            graph[x.first].push_back(x.second);
            graph[x.second].push_back(x.first);
        }
        queue<int> que;que.push(-1);/// init queue with -1, -1 is a separator
        for(int i = 0; i < n; i++)
            if(degree[i] == 1)
                que.push(i);
        for(int i = 2; i < n; i++){/// There are 2 MHTs at most;
            int now = que.front();que.pop();
            if(now == -1)
                que.push(-1),i--;/// push back the separator
            else
                for(const auto & x:graph[now])
                    if(--degree[x] == 1)
                        que.push(x);
        }
        while(que.front()!=-1) que.pop();
        que.pop();/// pop out the separator, the rest is the result.
        while(!que.empty())
            ret.push_back(que.front()),que.pop();
        return ret.size()?ret:vector<int>{0};
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.