想要精通算法和SQL的成长之路

算法和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;}
}