[leetcode] 310. Minimum Height Trees


Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Hint:

  1. How many MHTs can a graph have at most?

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Show Tags
Show Similar Problems
DP + DFS
Algorithm is as follows, but it is too slow. It costs about 1600ms to execute.
820495991460149548
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;
    }
};

Minimum height Trees - Performance of DFS with DP

Topological sort like algorithm. O(V+E)

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%.

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.