/**
1. 树的最长路径是一棵树的直径, 只要让直径最短, 那么高度也会最短, 所以取直径的中点作为根高度最短
2.1 bfs找到直径: 从任意一个点x搜索能到到的最远的点y, 再从y搜索到达最远的点z, y到z的路径即为直径; 返回直径中点, 偶数返回2个
2.2 拓扑排序: 每次删除度为1的点, 直到剩下1或2个点为止, 所求即为直径的中点
*/

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        Map<Integer, Set<Integer>> graph = build(edges);
        // return search(graph);
        return topSort(graph, edges);
    }

    public List<Integer> topSort(Map<Integer, Set<Integer>> graph, int[][] edges){
        List<Integer> list = new ArrayList<>();
        if (edges.length == 0) {
            list.add(0);
            return list;
        }

        Map<Integer, Integer> degree = new TreeMap<>();
        for (int i = 0 ; i< edges.length ; i++){
            int x = edges[i][0];
            int y = edges[i][1];
            if (degree.get(x) == null) degree.put(x, 0);
            if (degree.get(y) == null) degree.put(y, 0);
            degree.put(x, degree.get(x) + 1);
            degree.put(y, degree.get(y) + 1);
        }

        while (degree.size() > 2){
            for (Integer x : degree.keySet()) if (degree.get(x) == 1 ) list.add(x);

            for (int i = 0 ; i < list.size(); i++){
                int x = list.get(i);
                Set<Integer> edge = graph.get(x);
                if (edge == null) continue;
                for (Integer y : edge) {
                    if (degree.get(y) == null) continue;
                    degree.put(y, degree.get(y) - 1);
                }
                degree.remove(x);
                graph.remove(x);
            }
        }
        list.clear();
        for (Integer x : degree.keySet()) list.add(x);
        return list;
    }

    public Map<Integer, Set<Integer>> build(int[][] edges){
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0 ; i < edges.length ; i ++){
            int x = edges[i][0];
            int y = edges[i][1];
            if (graph.get(x) == null) graph.put(x, new TreeSet<>());
            graph.get(x).add(y);
            if (graph.get(y) == null) graph.put(y, new TreeSet<>());
            graph.get(y).add(x);
        }
        return graph;
    }

    public List<Integer> search(Map<Integer, Set<Integer>> graph){
        List<Integer> path = search(graph, 0);
        path = search(graph, path.get(0));
        int len = path.size();
        List<Integer> res = new ArrayList<>();
        res.add(path.get(len >> 1));
        if (len % 2 == 0) res.add(path.get(len / 2 - 1));
        if (res.size() > 1 && res.get(0) > res.get(1)) Collections.swap(res, 0, 1);
        return res;
    }

    public List<Integer> search(Map<Integer, Set<Integer>> graph, Integer start){
        Map<Integer, Integer> prev = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        prev.put(start, start);
        int top = start;
        while (!queue.isEmpty()){
            top = queue.poll();
            Set<Integer> edge = graph.get(top);
            if (edge == null || edge.isEmpty()) continue;
            for (Integer e : edge){
                if (prev.get(e) != null) continue;
                prev.put(e, top);
                queue.offer(e);
            }
        }
        List<Integer> path = new ArrayList<>();
        while(prev.get(top) != top){
            path.add(top);
            top = prev.get(top);
        }
        path.add(top);
        return path;
    }
}