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.

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.

题目来自leetcode, lint上面没有。

分析：

有两种方法可以做，解法2最直观，用每个点当root遍历一次，算出height，总共的复杂度是O(n^2);

解法1不容易想到但是更快，就是用bfs按顺序删除leaf结点（只有一个neighbor的点）在删光了之前的倒数第二次，记录结果就是所求的res。这是个O(n)的算法。

解法1：

小技巧：在建立adjacent list的时候，以前用的都是vector<vector<int> >
这道题目涉及到删除特定值了操作，所以用了个vector<unordered_set<int> >
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if (n == 0) {
            return vector<int>();
        }
        if (n == 1) {
            return vector<int>(1, 0);
        }

        vector<unordered_set<int> > neighbors(n, unordered_set<int>() );
        for (int i = 0; i < edges.size(); i++) {
            int first = edges[i].first;
            int second = edges[i].second;
            neighbors[first].insert(second);
            neighbors[second].insert(first);
        }

        vector<int> curr;
        for (int i = 0; i < n; i++) {
            if (neighbors[i].size() == 1) {
                curr.push_back(i);
            }
        }

        while(1) {
            vector<int> next;
            for (int i : curr) {
                for (int j : neighbors[i]) {
                    neighbors[j].erase(i);
                    if (neighbors[j].size() == 1) {
                        next.push_back(j);
                    }
                }
            }
            if (next.empty() ) {
                break;
            }
            curr = next;
        }
        return curr;
    }
};

解法2：

class Solution {
public:
    void bfsGetHeight(int i, vector<vector<int> > &neighbors, vector<int> &heights) {
        queue<int> Q;
        Q.push(i);
        vector<bool> visited(neighbors.size(), false);
        visited[i] = true;
        int height = 0;
        while (!Q.empty() ) {
            int size = Q.size();
            height++;
            for (int j = 0; j < size; j++) {
                int temp = Q.front();
                Q.pop();
                for (int k = 0; k < neighbors[temp].size(); k++) {
                    if (visited[neighbors[temp][k] ] == false) {
                        Q.push(neighbors[temp][k]);
                        visited[neighbors[temp][k] ] = true;
                    }
                }
            }
        }
        heights[i] = height;
    }

    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<vector<int> > neighbors(n, vector<int>() );
        vector<bool> visited(n, false);
        for (int i = 0; i < edges.size(); i++) {
            int first = edges[i].first;
            int second = edges[i].second;
            neighbors[first].push_back(second);
            neighbors[second].push_back(first);
        }
        vector<int> heights(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            bfsGetHeight(i, neighbors, heights);
        }
        int minHeight = INT_MAX;
        for (int i = 0; i < heights.size(); i++) {
            minHeight = min(minHeight, heights[i]);
        }
        vector<int> res;
        for (int i = 0; i < heights.size(); i++) {
            if (heights[i] == minHeight) {
                res.push_back(i);
            }
        }
        return res;
    }
};