[leetcode]Minimum Height Trees

这条题考的就是对graph和tree的熟悉程度... 记着tree maximum只可能有2个nodes能成为最短path的root... 围绕着这个做文章.. 不停地删leaf..剩下的（小于等于2）的结果就是所要的结果了..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

public class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { int degree[] = new int[n]; HashMap<Integer, List<Integer>> nodes = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < edges.length; i++){ int a = edges[i][0]; int b = edges[i][1]; List<Integer> listA = nodes.containsKey(a)?nodes.get(a):new ArrayList<Integer>(); List<Integer> listB = nodes.containsKey(b)?nodes.get(b):new ArrayList<Integer>(); listA.add(b); listB.add(a); nodes.put(a, listA); nodes.put(b, listB); degree[a]++; degree[b]++; } int remain = n; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < n; i++){ if(degree[i] == 1) queue.add(i); } while (remain > 2){ int size = queue.size(); for (int i = 0; i < size; i++){ int leaf = queue.poll(); remain--; degree[leaf]--; for (Integer neighbor:nodes.get(leaf)){ degree[neighbor]--; if (degree[neighbor] == 1) queue.add(neighbor); } } } List<Integer> result = new ArrayList<Integer>(queue); if (n == 1) result.add(0); return result; } }