310. Minimum Height Trees

Since this undirected graph has tree characteristics, any node in the graph can be a root and the graph mustn't have cycle. Since every node can be a root, the root with minimum height must have maximum leaves. So the problem becomes trimming the leaves level by level. The intuition about the level by level traversal is BFS. And yes, this problem can be solved by BFS.

However, when implementing, there are many places that are easy to make mistakes. I've highlighted them with red.

1:  class Solution {  
2:  public:  
3:    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {  
4:      vector<unordered_set<int>> adj(n);  
5:      vector<int> cur;  
6:      for (int i = 0; i < edges.size(); i++) {  
7:        adj[edges[i].first].insert(edges[i].second);  
8:        adj[edges[i].second].insert(edges[i].first);  
9:      }  
10:      for (int i = 0; i < n; i++) {  
11:        if (adj[i].size() == 1) {  
12:          cur.push_back(i);  
13:        }  
14:      }  
15:      if (n == 1) {  
16:        cur.push_back(0);  
17:        return cur;  
18:      }  
19:      while (true) {  
20:        vector<int> next;  
21:        for (int i : cur) {  
22:          for (int j : adj[i]) {  
23:            adj[j].erase(i);  
24:            if (adj[j].size() == 1) next.push_back(j);  
25:          }  
26:        }  
27:        if (next.empty()) break;  
28:        cur = next;  
29:      }  
30:      return cur;  
31:    }  
32:  };  

(1) this is an undirected graph, the adjacent list should reflect this.
(2) To check if a node is a leaf, we need to check the size of unordered_set is 1 (not 0) because the set should only include its parent.
(3) It's better to use for loop in the way above as it's more clear and also a convention to iterate unordered_set.