310. Minimum Height Trees

Link

Solution

從leaf(degree == 1的node) 開始，每次前進一格，直到沒尋訪到的node數目剩下一個or兩個。

implementation重點:

1. 用Set[]紀錄所有node連結的點

2. 用set[i].size去知道degree狀態

3. 透過BFS來尋訪node

4. 當尋訪node時，要記得把跟node有連結的點的(connected set)更新，避免重複查找

  public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if(n == 1){
            List list = new LinkedList<Integer>();
            list.add(0);
            return list;
        }
        Set<Integer>[] graph = new HashSet[n];
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            graph[i] = new HashSet<Integer>();
            set.add(i);
        }
        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        //First run nodes
        for(int i = 0; i < n; i++){
            if(graph[i].size() == 1){
                queue.add(i);
            }
        }
        //BFS
        while(!queue.isEmpty()){
            if(set.size() <= 2){
                break;   
            }
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int element = queue.poll();
                set.remove(element);
                for(int con : graph[element]){
                    graph[con].remove(element);
                    if(graph[con].size() == 1){
                        queue.add(con);
                    }
                }
            }
        }
        return new LinkedList<Integer>(set);
        
    }