1068ms C++ Solution using xor with O(n) time and O(n) space


  • 0
    K
    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> xor_edges(n,0);
            vector<int> degrees(n,0);
            vector<int> result;
            int edgnum = edges.size();
            if(edgnum == 0){
                result.push_back(0);
                return result;
            }
            for(pair<int,int> e : edges){
                degrees[e.first] ++;
                degrees[e.second] ++;
                xor_edges[e.first] = xor_edges[e.first] ^ e.second;
                xor_edges[e.second] =xor_edges[e.second] ^ e.first;
            }
            int i;
            deque<int> queue;
            for( i=0 ; i<n ; i++){
                if(degrees[i] == 1){
                    queue.push_back(i);
                }
            }
            for( ; edgnum > 1; ){
                queue.push_back(-1);
                for(;;){
                    i = queue.front();
                    queue.pop_front();
                    if(i == -1)break;
                    degrees[i] --;
                    int j = xor_edges[i];
                    //xor_edges[i] = 0;
                    xor_edges[j] ^= i;
                    degrees[j]--;
                    if(degrees[j] == 1){
                        queue.push_back(j);
                    }
                    edgnum--;
                }
            }
            result.insert(result.end(),queue.begin(),queue.end());
            return result;
        }
        
    };

Log in to reply
 

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