# 0310. Minimum Height Trees
###### tags: `Leetcode` `FaceBook` `Topological Sort` `Medium`
Link: https://leetcode.com/problems/minimum-height-trees/
## 思路 $O(N)$ $O(N)$
参考[这个](https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts)
对于一个path graph，只要找到中间的点做root就可以
如果不知道path的长度，只需要用双指针，从两端开始移动，当它们meet或者只相差1，就找到root了
这题的tree也是一样

" 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."

当最后只剩下一个点或者两个点没有遍历的时候，他们就是root了
注意在while回圈不能用leaves.size()>2，如果是a->b,a->c的tree，还没开始做bfs，就return了

## Code

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n==1){
            List<Integer> ans = new ArrayList<>();
            ans.add(0);
            return ans;
        }
        List<Integer>[] graph = new List[n];
        for(int i = 0;i < edges.length;i++){
            int u = edges[i][0];
            int v = edges[i][1];
            if(graph[u]==null) graph[u] = new ArrayList<>();
            if(graph[v]==null) graph[v] = new ArrayList<>();
            graph[u].add(v);
            graph[v].add(u);
        }
        List<Integer> leaves = new ArrayList<>();
        for(int i = 0;i < n;i++){
            if(graph[i].size()==1) leaves.add(i);
        }
        while(n>2){
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for(int leave:leaves){
                int u = graph[leave].get(0);
                for(int i = 0;i < graph[u].size();i++){
                    if(graph[u].get(i)==leave){
                        graph[u].remove(i);
                        break;
                    }
                }
                if(graph[u].size()==1){
                    newLeaves.add(u);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}