leetcode解题: Minimum Height Trees (310)

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]

解法1： O(N) Time + O(N) Space

这题有些难度。。一开始自己想了O(N*N)的算法，果断TLE了。 这里的解法是参考了Discussion里的一个解法。
首先要观察， 看对于一个图最多有几个可能的MHT， 答案是最多有两个。 为什么呢？假设有1个，那么就是自己。
假设有两个节点，则无论他们是否连接， 其中任何一个作为节点高度都是一样的。
如果只有三个节点， 那么如果有两个线连着，那么有两个叶子和一个中间点，那个中间点就是MHT。
有了这个思路， 我们可以从leaf出发，不停的向图中间靠拢，直到没有leaf为止（leaf定义为有且仅有一条边界）/

C++

可以用unordered_set<int>来表示children， 对应的操作有erase（）， insert（）
C++中有std::swap可以用来交换两个container中的数据。
vector可以用vector.clear()来清除里面的数据。

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> res;
        if (n == 1) {
            res.push_back(0);
            return res;
        }

        if (n == 2) {
            res.push_back(0);
            res.push_back(1);
            return res;
        }

        // Construct the tree
        unordered_map<int, unordered_set<int>> map;
        for (auto p : edges) {
            if (!map.count(p.first)) {
                map[p.first] = unordered_set<int>();
            }
            if (!map.count(p.second)) {
                map[p.second] = unordered_set<int>();
            }
            map[p.first].insert(p.second);
            map[p.second].insert(p.first);
        }

        // Remove leaves until we have only 1 or 2 nodes
        vector<int> leaves;
        for (int i = 0; i < n; ++i) {
            if (map[i].size() == 1) {
                leaves.push_back(i);
            }
        }

        vector<int> newLeaves;
        while (true) {
            for (int leaf : leaves) {
                unordered_set<int> innerLayer = map[leaf];
                for (int node : innerLayer) {
                    map[node].erase(leaf);
                    if (map[node].size() == 1) {
                        newLeaves.push_back(node);
                    }
                }
            }
            if (newLeaves.empty()) {
                return leaves;
            }
            leaves.clear();
            swap(leaves, newLeaves);
        }
    }
};

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        if (n == 2) {
            res.add(0);
            res.add(1);
            return res;
        }
        if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
            return res;
        }

        // BFS and 剥洋葱
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge: edges) {
            int start = edge[0];
            int end = edge[1];
            if (!map.containsKey(start)) {
                map.put(start, new HashSet<>());
            }
            if (!map.containsKey(end)) {
                map.put(end, new HashSet<>());
            }
            map.get(start).add(end);
            map.get(end).add(start);
        }

        // Doing a bfs
        Queue<Integer> queue = new LinkedList<>();
        for (int key : map.keySet()) {
            if (map.get(key).size() == 1) {
                queue.offer(key);
            }
        }

        // Doing a peel-an-onion algorithm
        while ( n > 2) {
            int size = queue.size();    // number of leaf nodes at this time
            n -= size;
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                Set<Integer> connected = map.get(node);
                for (int c : connected) {
                    map.get(c).remove(node);
                    if (map.get(c).size() == 1) {
                        queue.offer(c); // next round onion peel
                    }
                }
            }
        }

        while (!queue.isEmpty()) {
            res.add(queue.poll());
        }
        return res;
    }
}