package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/minimum-height-trees/
 */
public class Problem310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        // TODO:
        return result;
    }

    public static void main(String[] args) {
        Problem310 prob = new Problem310();
        System.out.println(prob.findMinHeightTrees(4, new int[][]{
            {1, 0}, {1, 2}, {1, 3}
        })); // 1
        System.out.println(prob.findMinHeightTrees(6, new int[][]{
            {0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}
        })); // 3, 4
        System.out.println(prob.findMinHeightTrees(7, new int[][]{
            {0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}, {0, 6}
        })); // 3
    }
}

@@ -57,20 +57,94 @@
 va.util.
-List
+HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.TreeMap
 ;%0A%0A/**%0A 
@@ -307,87 +307,1881 @@
     
-List%3CInteger%3E result = new ArrayList%3C%3E();%0A        // TODO:%0A        return resul
+if (n %3C= 1) %7B%0A            return new ArrayList%3C%3E();%0A        %7D%0A        Map%3CInteger, List%3CInteger%3E%3E adjList = buildAdjList(edges);%0A        TreeMap%3CInteger, List%3CInteger%3E%3E result = new TreeMap%3C%3E();%0A        for (int i = 0; i %3C n; i++) %7B%0A            boolean%5B%5D visited = new boolean%5Bn%5D;%0A            int height = countHeight(i, adjList, visited, 0);%0A            if (!result.containsKey(height)) %7B%0A                List%3CInteger%3E list = new ArrayList%3C%3E();%0A                list.add(i);%0A                result.put(height, list);%0A            %7D else %7B%0A                result.get(height).add(i);%0A            %7D%0A        %7D%0A        return result.firstEntry().getValue();%0A    %7D%0A%0A    private int countHeight(int node, Map%3CInteger, List%3CInteger%3E%3E adjList, boolean%5B%5D visited,%0A                            int accu) %7B%0A        visited%5Bnode%5D = true;%0A        int maxHeight = accu;%0A        for (int n : adjList.get(node)) %7B%0A            if (!visited%5Bn%5D) %7B%0A                int height = countHeight(n, adjList, visited, accu + 1);%0A                maxHeight = Math.max(maxHeight, height);%0A            %7D%0A        %7D%0A        return maxHeight;%0A    %7D%0A%0A    private Map%3CInteger, List%3CInteger%3E%3E buildAdjList(int%5B%5D%5B%5D edges) %7B%0A        Map%3CInteger, List%3CInteger%3E%3E adjList = new HashMap%3C%3E();%0A        for (int i = 0; i %3C edges.length; i++) %7B%0A            int x = edges%5Bi%5D%5B0%5D;%0A            int y = edges%5Bi%5D%5B1%5D;%0A            if (!adjList.containsKey(x)) %7B%0A                List%3CInteger%3E list = new ArrayList%3C%3E();%0A                list.add(y);%0A                adjList.put(x, list);%0A            %7D else %7B%0A                adjList.get(x).add(y);%0A            %7D%0A%0A            if (!adjList.containsKey(y)) %7B%0A                List%3CInteger%3E list = new ArrayList%3C%3E();%0A                list.add(x);%0A                adjList.put(y, list);%0A            %7D else %7B%0A                adjList.get(y).add(x);%0A            %7D%0A        %7D%0A        return adjLis
 t;%0A 
@@ -2660,16 +2660,16 @@
  %7B0, 6%7D%0A
-
         
@@ -2678,16 +2678,101 @@
 ); // 3%0A
+        System.out.println(prob.findMinHeightTrees(1, new int%5B%5D%5B%5D%7B%0A        %7D)); // 0%0A
     %7D%0A%7D%0A

Update problem 310