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]

Tips:

思路

1.类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点。

2.先建立 List<HashSet<Integer>> adjacent， 来存储所有点的edge。
  实际是建立一个类似hashmap的东西，用ArrayList里面的位置（index）来作为key, 所以可以使用get(edge[0])这种来添加edge。

3.然后找出所有的叶子节点，即set.size() == 1的点，将这些点加入叶子节点的ArrayList。

4.之后进入循环，在n > 2的条件下一层一层把叶子节点剥掉。ArrayList newLeave来作为下一层叶子节点，取代leaves，再剥。

注意点

 1.return Collections.singletonList(0);   singletonList

 2.int neighbor = adjacent.get(leave).iterator().next(); 这是hashset里面往下一个的办法

The time complexity and space complexity are both O(n).

We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

It is easy to see that the last two pointers are from the two ends of the longest path in the graph.

The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What's left is our answer! Note that for a tree we always have V = n, E = n-1.

Code:

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Collections.singletonList(0);
        }
        List<HashSet<Integer>> adjacent = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacent.add(new HashSet<Integer>());
        }
        //add edges to each node
        for (int[] edge : edges) {
            adjacent.get(edge[0]).add(edge[1]);
            adjacent.get(edge[1]).add(edge[0]);
        }
        // Through set.size() to judge if the node is a leave
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (adjacent.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        while (n > 2) {
            List<Integer> newLeaves = new ArrayList<>();
            for (int leave : leaves) {
                int neighbor = adjacent.get(leave).iterator().next();
                adjacent.get(neighbor).remove(leave);
                n--;
                if (adjacent.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}