DP + DFS

Algorithm is as follows, but it is too slow. It costs about 1600ms to execute.

class Solution {
public:
    int MAX_INT = 0x7fffffff;
    unordered_map<int, unordered_map<int, int>> heights;// store heights given vertex and edge
    unordered_map<int, vector<int> >graph;
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        int height = MAX_INT;
        vector<int> res;
        // build graph
        graph.clear();
        heights.clear();
        for(auto it = edges.begin(); it != edges.end(); it++){
            if(graph.find(it->first) == graph.end()){
                graph[it->first] = vector<int>();
            }
            if(graph.find(it->second) == graph.end()){
                graph[it->second] = vector<int>();    
            }
            graph[it->first].push_back(it->second);
            graph[it->second].push_back(it->first);
        }
        
        // for each vertex in graph
        for(int i = 0; i < n; i++){
            int localHeight = 0;
            for(auto it = graph[i].begin(); it != graph[i].end(); it++){
                localHeight = max(localHeight, _MHT(i, *it));
            }
            if(height == localHeight){
                res.push_back(i);
            }else if(localHeight < height){
                res.clear();
                res.push_back(i);
            }
            height = min(localHeight, height);
        }
        return res;
    }
    //pv : previous vertex, v: current vertex
    int _MHT(int pv, int v){
        int h = getHeight(pv, v);
        if(h >= 0){
            return h;
        }
        else{
            h = 0;
            for(auto it = graph[v].begin(); it != graph[v].end(); it++){
                if(*it != pv){
                    h = max(_MHT(v, *it) + 1, h);
                }
            }
            setHeight(pv, v, h);
            return h;
        }
    }
    
    int getHeight(int pv, int v){
        if(heights.find(pv) == heights.end() || heights[pv].find(v) == heights[pv].end()){
            return -1;
        }else{
            return heights[pv][v];
        }
    }
    void setHeight(int pv, int v, int h){
        if(heights.find(pv) == heights.end()){
            heights[pv] = unordered_map<int, int>();
        }
        heights[pv][v] = h;
    }
};

A better, easier to understand solution

We perform topological sort to the given graph. The rest elements in the last iteration are what we want. We can even find them without calculate their minimum height!

In this question, the given tree-like graph is an undirected graph, but topological sort is applicable only to directed graph. We have to modify the original topological sort algorithm. Different from a typical topological sort algorithm which is described in wikipedia https://en.wikipedia.org/wiki/Topological_sorting . We maintain two queues – readyQ and runningQ – in the algorithm. This idea is inspired by the process states (ready, running, block, zombie) in operating systems. Each time when runningQ is empty, we check whether we have ever pushed all vertices in either queue, which is indicated by restN == 0. If restN == 0, elements in readyQ is what we want. Otherwise, we swap readyQ and runningQ and enter the next iteration.

// Topological sort
// O(V+E)
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        unordered_map<int, unordered_set<int>> graph;
        vector<int> inDegree = vector<int>(n, 0);
        vector<int> res;
        // extreme case
        if(n == 1){
            res.push_back(0);
            return res;
        }
        // build indegree vector
        for(auto it = edges.begin(); it != edges.end(); it++){
            inDegree[it->first]++;
            inDegree[it->second]++;
            if(graph.find(it->first) == graph.end()){
                graph[it->first] = unordered_set<int>();
            }
            if(graph.find(it->second) == graph.end()){
                graph[it->second] = unordered_set<int>();
            }
            graph[it->first].insert(it->second);
            graph[it->second].insert(it->first);
        }
        // find all vetices with indegree 1
        int restN = n;
        queue<int> readyQ, runningQ;
        for(int i = 0; i < n; i++){
            if(inDegree[i] == 1){
                readyQ.push(i);
                restN--;
            }
        }
        // finish, vertices in readyQ are the answer
        while(restN > 0){
            runningQ = readyQ;
            // clear readyQ;
            readyQ = queue<int>();
            while(!runningQ.empty()){
                int v = runningQ.front();
                runningQ.pop();
                for(auto it = graph[v].begin(); it != graph[v].end(); it++){
                    if(--inDegree[*it] == 1){
                        readyQ.push(*it);
                        restN--;
                    }
                    // remove edge
                    graph[*it].erase(v);
                }
            }
        }
        while(!readyQ.empty()){
            res.push_back(readyQ.front());
            readyQ.pop();
        }
        return res;
    }
};

The performance is slightly improved by 20%.