用dw建设网站,外贸做的亚马逊网站是哪个好,信息发布网站有哪些,wordpress缩略图质量310. 最小高度树
解题思路 首先#xff0c;在方法的开头#xff0c;创建了一个空的列表res#xff0c;用于存储最小高度树的根节点。 接着#xff0c;通过条件判断#xff0c;检查如果图中只有一个节点#xff08;即n 1#xff09;#xff0c;则将该节点添加到结果列…310. 最小高度树
解题思路 首先在方法的开头创建了一个空的列表res用于存储最小高度树的根节点。 接着通过条件判断检查如果图中只有一个节点即n 1则将该节点添加到结果列表中并返回结果。 然后创建了一个长度为n的整型数组degree用于存储每个节点的出度。 接下来创建了一个二维列表map表示图的邻接表用于存储节点之间的连接关系。对于每个节点初始化一个空列表。 然后遍历边数组edges更新节点的出度和邻接表。对于每条边将边的起始节点和终止节点的出度加1并将终止节点加入起始节点的邻接表中将起始节点加入终止节点的邻接表中。 接着创建了一个队列queue用于执行广度优先搜索。将所有出度为1的叶子节点入队。 在队列不为空的情况下进行循环。在每次循环中创建一个新的空列表res用于存储当前层的节点。 然后获取队列的当前大小表示当前层的节点数。对于当前层的每个节点将其从队列中取出并添加到res列表中。 接着获取当前节点的邻居节点列表并遍历这些邻居节点。对于每个邻居节点将其出度减1并检查如果其出度变为1则将其加入队列中以便下一层的遍历。 最后返回结果列表res其中包含了所有最小高度树的根节点。 ****class Solution {public ListInteger findMinHeightTrees(int n, int[][] edges) {ListInteger res new ArrayList();// 如果只有一个节点if(n 1){res.add(0);return res;}int[] degree new int[n];// 节点的出度表// 建立图关系ListListInteger map new ArrayList();for(int i 0; i n; i){map.add(new ArrayList());}for(int[] edge:edges){degree[edge[0]];// 边的起始点degree[edge[1]];// 边的终止点map.get(edge[0]).add(edge[1]);map.get(edge[1]).add(edge[0]);}// 建立队列QueueInteger queue new LinkedList();// 所有叶子节点 入队 出度为1的节点 for(int i 0; i n; i){if(degree[i] 1){queue.offer(i);}}while(!queue.isEmpty()){res new ArrayList();int size queue.size();for(int i 0; i size; i){int cur queue.poll();res.add(cur);ListInteger neighbors map.get(cur);for (int neighbor : neighbors) {degree[neighbor]--;if (degree[neighbor] 1) {/*如果是叶子节点我们就入队*/queue.offer(neighbor);}}}}return res;}
}
