河北手机网站建设百度扫一扫识别图片在线

class Solution {public List<Integer> findMinHeightTrees(int n, int[][] edges) {//如果一个节点连接的节点越多 也就是这个节点的度越高 将这样的节点作为根节点 形成的树的高度越小//首先让叶子节点(度为1的节点)先进队列 然后将它们移除队列 找到它们的邻居节点//将邻居节点的度数减一 如果这时邻居节点度数有变成一的 让它们也进队列//如此反复下去 队列里只可能有 1个或2个节点 也就是最后的答案List<Integer> res = new ArrayList<>();if(n == 1)//只有一个节点 直接返回这个节点就可以啦{res.add(0);return res;}int[] degree = new int[n];//存放每个节点的度List<List<Integer>> list = new ArrayList<List<Integer>>();//存放每个节点 连接的节点for(int i=0;i<n;i++)list.add(new ArrayList<>());for(int i=0;i<edges.length;i++){degree[edges[i][0]] += 1;degree[edges[i][1]] += 1;list.get(edges[i][0]).add(edges[i][1]);list.get(edges[i][1]).add(edges[i][0]);}//创建一个队列Queue<Integer> queue = new LinkedList<Integer>();//将度为1的节点入队列for(int i =0;i<n;i++){if(degree[i] == 1){queue.offer(i);// degree[i] -= 1;}    }while(queue.size() != 0){res = new ArrayList<>();//存放每一轮的叶子节点 最后一轮的叶子节点即为答案int size = queue.size();for(int i=0;i<size;i++){int cur = queue.poll();res.add(cur);List<Integer> l = list.get(cur);//获得cur节点的邻居节点for(int j = 0;j < l.size();j ++){degree[l.get(j)] -=1;//将邻居节点的度减一if(degree[l.get(j)] == 1)//如果度为1 则加入队列queue.offer(l.get(j));}}}return res;}
}