310. 最小高度树

描述

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

分析

度的是无向图中一个结点与多少个其他节点相连接。

最小高度树 根结点一定是处于图的最中间的位置，因为只有在最中间，它去往其他节点的长度最短。每次把度为1的结点删除掉，也就是把最外面一层的结点删除掉，向内部逼近，就像是在剥洋葱。最后剩下两个或一个度为1的结点，则该节点便是最小高度树的根节点。

建一个数组记录度 一个链表记录一个结点与之相连接的其他节点 队列存储度为0的结点
判断一个结点是不是叶子节点：看它的度是否为1
剪去最外面一层的结点，即把度为1的结点加入队列，弹出队列中的元素，同时把他们自己及其与他们相连接的结点的度减1.
在减去外面一层结点的时候，同时把度为1的结点加入到队列当中。
最小高度树的根节点: 当前队列存储的叶子结点弹出后，做了相邻节点的度减1操作，但是没有新的叶子节点加入进来，说明已经到头了，即此轮队列里的结点是最小高度树的根节点

public class MinestTree {public List<Integer> findMinHeightTrees(int n, int[][] edgs){List<Integer> res = new ArrayList<>();if(n == 1){res.add(0);return res;}int[] degree = new int[n];List<List<Integer>> adjoin = new ArrayList<>();for(int i = 0; i < n; i++){adjoin.add(new ArrayList<>());}for(int[] arr : edgs){degree[arr[0]]++;degree[arr[1]]++;adjoin.get(arr[0]).add(arr[1]);adjoin.get(arr[1]).add(arr[0]);}Queue<Integer> que = new LinkedList<>();for(int i = 0; i < n; i++){if(degree[i] == 1){que.add(i);}}while(!que.isEmpty()){//que不为空，说明还有叶子节点，即上一轮的叶子节点一定不是根节点，所以清理掉。res.clear();int size = que.size();for(int i = 0; i < size; i++){int num = que.poll();res.add(num);degree[num]--;List<Integer> li = adjoin.get(num);for(int lis : li){degree[lis]--;if(degree[lis] == 1){que.add(lis);}}}}//队列没有元素跳出循环时，res保存了最后一轮循环的元素值，即根节点。return res;}
}