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

• ``````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;
}

};``````

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