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 containsnnodes which are labeled from0ton - 1. You will be given the numbernand a list of undirectededges(each edge is a pair of labels).

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

Example 1:

Givenn = 4,edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return[1]

Example 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return[3, 4]

Solution 1: MHT的根一定是最长路径的中点。先以任意点为起点，BFS找到最长路径终点；再以这终点为起点，BFS找到最长路径。根就是这条路径的中点。

    int n;
    List<Integer>[] edge;

    private void bfs(int start, int[] distance, int[] preNode) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        distance[start] = 0;
        visited[start] = true;
        preNode[start] = -1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : edge[u])
                if (!visited[v]) {
                    visited[v] = true;
                    distance[v] = distance[u] + 1;
                    queue.add(v);
                    preNode[v] = u;
                }
        }
    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n <= 0) return ans;
        this.n = n;
        edge = new List[n];
        for (int i = 0; i < n; i++)
            edge[i] = new ArrayList<>();
        for (int[] pair : edges) {
            int u = pair[0];
            int v = pair[1];
            edge[u].add(v);
            edge[v].add(u);
        }

        int[] distance1 = new int[n];
        int[] distance2 = new int[n];
        int[] preNode = new int[n];

        bfs(0, distance1, preNode);
        int u = 0;
        for (int i = 0; i < n; i++)
            if (distance1[i] > distance1[u]) u = i;

        bfs(u, distance2, preNode);
        int v = 0;
        for (int i = 0; i < n; i++)
            if (distance2[i] > distance2[v]) v = i;

        List<Integer> list = new ArrayList<>();
        while (v != -1) {
            list.add(v);
            v = preNode[v];
        }

        if (list.size() % 2 == 1) {
            ans.add(list.get(list.size() / 2));
        } else {
            ans.add(list.get(list.size() / 2 - 1));
            ans.add(list.get(list.size() / 2));
        } 
        return ans;
    }

Solution 2: 从叶子节点出发，一层一层往内删，每次删去所有叶子节点，直到只剩一个或两个点，即roots

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);

    List<Set<Integer>> adj = new ArrayList<>(n);
    for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; ++i)
        if (adj.get(i).size() == 1) leaves.add(i);

    while (n > 2) {
        n -= leaves.size();
        List<Integer> newLeaves = new ArrayList<>();
        for (int i : leaves) {
            int j = adj.get(i).iterator().next();
            adj.get(j).remove(i);
            if (adj.get(j).size() == 1) newLeaves.add(j);
        }
        leaves = newLeaves;
    }
    return leaves;
}

TLE: 对每个点做BFS求高度会超时

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
            ans.add(0);
            return ans;
        }
        Map<Integer, List<Integer>> hashmap = new HashMap<>();
        for (int[] edge : edges) {
            List<Integer> list = hashmap.get(edge[0]);
            if (list == null) {
                list = new ArrayList<>();
                list.add(edge[1]);
                hashmap.put(edge[0], list);
            } else {
                list.add(edge[1]);
            }
            list = hashmap.get(edge[1]);
            if (list == null) {
                list = new ArrayList<>();
                list.add(edge[0]);
                hashmap.put(edge[1], list);
            } else {
                list.add(edge[0]);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int level = 0;
            Queue<Integer> queue = new LinkedList<>();
            boolean[] visited = new boolean[n];
            queue.add(i);
            visited[i] = true;
            while (!queue.isEmpty()) {
                int size = queue.size();
                level++;
                if (level > min) {
                    break;
                }
                for (int j = 0; j < size; j++) {
                    int cur = queue.poll();
                    for (int neighbour : hashmap.get(cur)) {
                        if (!visited[neighbour]) {
                            queue.offer(neighbour);
                            visited[neighbour] = true;
                        }
                    }
                }
            }
            if (level == min) {
                ans.add(i);
            } else if (level < min) {
                ans.clear();
                ans.add(i);
                min = level;
            }
        }
        return ans;
    }