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]

Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactlyone 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.

Solution1：Literally find Longest Path by BFS

思路： 隨便選一點a，從a bfs先找出距a的最遠(yuǎn)的u，再從u點bfs找出最遠(yuǎn)點v，u到v的path的一半處就是result.
Time Complexity: O(N) Space Complexity: O(N)
Note: DFS 1.b 這這里其實也可以

Solution2：BFS topological sort

思路： 類似Undirected拓?fù)渑判驅(qū)Σ連FS方法，從pointers所有l(wèi)eaves向內(nèi)，當(dāng)兩個pointers met，only keep one of them, until the last two pointers meet or one step away we then find the roots.

(1) 在做UnDirected 拓?fù)渑判驎r，要避免訪問前驅(qū)：
實現(xiàn)1：采用在adj_list.get(cur).remove(prev)的方式，因為(1)，所以remove是O(1), 且這樣就不需要使用indegree數(shù)組，adj_list.get(cur).size()就可以作為indegree作用。
（實現(xiàn)2: 不remove，通過visited數(shù)組，但額外需要indegree數(shù)組，因為adj_list.get(cur).size()不能再作為indegree作用?？梢詉ndegree數(shù)組／visited數(shù)組通過共同一個數(shù)組表示。）因為下述(2)，肯定是訪問到的是 prev->cur->next形式，所以remove是O(1)，實現(xiàn)1比較好

(2) 在做UnDirected 拓?fù)渑判驎r，訪問到的indegree = 1的node，最多肯定只有一個前驅(qū)和一個后繼，所以不需要遍歷list來拿到nexts，只有一個next，直接可以通過adj.get(u).iterator().next();

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!

Time Complexity: O(N) Space Complexity: O(N)

Solution3：Tree DP??

思路： (temporarily skip)
reference: https://leetcode.com/problems/minimum-height-trees/discuss/
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

public class Solution {
    int n;
    List<List<Integer>> graph;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n <= 0) return new ArrayList<>();
        this.n = n;
        
        // build graph
        graph = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int[] pair : edges) {
            int u = pair[0];
            int v = pair[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        int[] dist1 = new int[n]; // dist for all node from u
        int[] dist2 = new int[n]; // dist for all node from v
        int[] pre = new int[n]; // precursor array: v: u
        
        // get far end1 = u
        bfs(0, dist1, pre);
        int u = 0;
        for (int i = 0; i < n; i++)
            if (dist1[i] > dist1[u]) u = i;

        // get far end2 = v
        bfs(u, dist2, pre);
        int v = 0;
        for (int i = 0; i < n; i++)
            if (dist2[i] > dist2[v]) v = i;

        // prepare the result: add path from u to v to list
        List<Integer> list = new ArrayList<>();
        while (v != -1) {
            list.add(v);
            v = pre[v];
        }

        // return the result
        if (list.size() % 2 == 1) return Arrays.asList(list.get(list.size() / 2));
        else return Arrays.asList(list.get(list.size() / 2 - 1), list.get(list.size() / 2));
    }
    
    
    private void bfs(int start, int[] dist, int[] pre) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        visited[start] = true;
        dist[start] = 0;
        pre[start] = -1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u))
                if (!visited[v]) {
                    dist[v] = dist[u] + 1;
                    queue.add(v);
                    visited[start] = true;
                    pre[v] = u;
                }
        }
    }
}

Solution1.b Code：

class Solution {
    
    class Pack {
        public int far_id;
        public int max_len;
        
        Pack() {
            far_id = -1;
            max_len = 0;
        }
    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(edges == null || edges.length == 0) {
            if(n == 1) return Arrays.asList(0);
            else return new ArrayList<>();
        }
        
        // graph
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for(int i = 0; i < edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        
        int[] pre = new int[n];
        Arrays.fill(pre, -1);
        
        Pack pack1 = dfs(graph, edges[0][0], -1, pre);
        Pack pack2 = dfs(graph, pack1.far_id, -1, pre);
        
        List<Integer> list = new ArrayList<>();
        
        pack1.max_len -= 1;
        pack2.max_len -= 1;

        int v = pack2.far_id;
        while (v != -1) {
            System.out.println("v: " + v);
            list.add(v);
            v = pre[v];
        }
        
        // prepare result
        if(list.size() % 2 == 1) {
            return Arrays.asList(list.get(list.size() / 2));
        }
        else {
            return Arrays.asList(list.get(list.size() / 2 - 1), list.get(list.size() / 2));
        }
    }
    
    
    private Pack dfs(List<List<Integer>> graph, int start_id, int prev, int[] pre) {
        Pack cur_pack = new Pack();
        if(graph.get(start_id).size() == 1) {
            // leaf
            cur_pack.far_id = start_id;
        }
        pre[start_id] = prev;
        
        List<Integer> next_list = graph.get(start_id);
        for(int next: next_list) {
            if(next == prev) continue;
            Pack pack = dfs(graph, next, start_id, pre);
            if(pack.max_len > cur_pack.max_len) {
                cur_pack.max_len = pack.max_len;
                cur_pack.far_id = pack.far_id;
            }
        }
        
        cur_pack.max_len++;
        return cur_pack;
    }
}

Solution2 Code：

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Arrays.asList(0);
        // if (n == 2) return Arrays.asList(0, 1);
        
        // graph: adj_list init
        List<List<Integer>> adj = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++) {
            adj.add(new ArrayList<Integer>()); 
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        

        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (adj.get(i).size() == 1) leaves.offer(i);
        }
        
        while (n > 2) {
            int num_leaves = leaves.size();
            n -= num_leaves;
            for(int i = 0; i < num_leaves; i++) {
                int u = leaves.poll();
                int v = adj.get(u).iterator().next();
                adj.get(v).remove(new Integer(u)); // remove by finding value.
                if (adj.get(v).size() == 1) leaves.add(v);
            }
        }
        return (List)leaves;
    }

}

Solution3 Code：