算法和SQL的成长之路"/>
想要精通算法和SQL的成长之路
想要精通算法和SQL的成长之路 - 最小高度树
- 前言
- 一. 最小高度树
- 1.1 邻接表的构建
- 1.2 入度为1的先入队
- 1.3 BFS遍历
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 最小高度树
原题链接
从题目的含义中我们可以发现:
- 题目的树是一颗多叉树。
- 叶子节点的度为1,而非叶子节点的度至少是2(多叉树)
- 树的高度由根节点到叶子节点的最大距离决定。
题目要求返回根节点列表,那么我们很难自上而下的遍历。那么不妨我们从叶子节点入手,自下而上的遍历呢?
- 我们构建邻接表和一个度数组。
- 我们把度为1的节点(叶子节点)入队。
- 每层遍历,把队列中的节点移除,并根据邻接表拿到他们的相邻节点。并且更新他们的度(-1),若度在减1之后,为1,继续把他们丢到队列,进入下一层循环。
- 那么最终留下来的就是根节点列表。
1.1 邻接表的构建
// 构建邻接表和出度数组
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());
}
int[] degree = new int[n];
for (int[] edge : edges) {// 一条边的两个端点,都要计算度以及构建对应的邻接关系degree[edge[0]]++;degree[edge[1]]++;adj.get(edge[0]).add(edge[1]);adj.get(edge[1]).add(edge[0]);
}
1.2 入度为1的先入队
// 出度为1的入队
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {if (degree[i] == 1) {queue.offer(i);}
}
1.3 BFS遍历
while (!queue.isEmpty()) {// 清空数组,每层遍历,res存储的都是res.clear();int size = queue.size();for (int i = 0; i < size; i++) {// 从队列中移除一个度为1的元素并把它加入到结果集Integer cur = queue.poll();res.add(cur);// 根据当前元素,拿到与他的邻接元素List<Integer> nextNode = adj.get(cur);// 更新邻接元素的度,如果度-1之后,为1,说明它是新的叶子节点(老的我们直接删除),继续丢到队列,进入下一层循环for (Integer next : nextNode) {degree[next]--;if (degree[next] == 1) {queue.offer(next);}}}
}
// 到这里,res留下的就是根节点
return res;
完整代码如下:
public class Test310 {public List<Integer> findMinHeightTrees(int n, int[][] edges) {ArrayList<Integer> res = new ArrayList<>();// 如果只有一个节点,直接返回根节点0if (n == 1) {res.add(0);return res;}// 构建邻接表和出度数组List<List<Integer>> adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}int[] degree = new int[n];for (int[] edge : edges) {degree[edge[0]]++;degree[edge[1]]++;adj.get(edge[0]).add(edge[1]);adj.get(edge[1]).add(edge[0]);}// 出度为1的入队LinkedList<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (degree[i] == 1) {queue.offer(i);}}while (!queue.isEmpty()) {// 清空数组,每层遍历,res存储的都是res.clear();int size = queue.size();for (int i = 0; i < size; i++) {// 从队列中移除一个度为1的元素并把它加入到结果集Integer cur = queue.poll();res.add(cur);// 根据当前元素,拿到与他的邻接元素List<Integer> nextNode = adj.get(cur);// 更新邻接元素的度,如果度-1之后,为1,说明它是新的叶子节点(老的我们直接删除),继续丢到队列,进入下一层循环for (Integer next : nextNode) {degree[next]--;if (degree[next] == 1) {queue.offer(next);}}}}// 到这里,res留下的就是根节点return res;}
}
更多推荐
想要精通算法和SQL的成长之路
发布评论