题目

类型：DFS、BFS

image.png

解题思路

1、首先，我们看了样例，发现这个树并不是二叉树，是多叉树。
2、然后，我们可能想到的解法是：根据题目的意思，就挨个节点遍历bfs，统计下每个节点的高度，然后用map存储起来，后面查询这个高度的集合里最小的就可以了。
3、但是这样会超时的。
4、于是我们看图（题目介绍里面的图）分析一下，发现，越是靠里面的节点越有可能是最小高度树。
5、所以，我们可以这样想，我们可以倒着来。
6、我们从边缘开始，先找到所有出度为1的节点，然后把所有出度为1的节点进队列，然后不断地bfs，最后找到的就是两边同时向中间靠近的节点，那么这个中间节点就相当于把整个距离二分了，那么它当然就是到两边距离最小的点啦，也就是到其他叶子节点最近的节点了。
7、然后，就可以写代码了。

代码

  1. class Solution {
  2.   public List<Integer> findMinHeightTrees(int n, int[][] edges) {
  3.         List<Integer> res = new ArrayList<>();
  4.         /*如果只有一个节点，那么他就是最小高度树*/
  5.         if (n == 1) {
  6.             res.add(0);
  7.             return res;
  8.         }
  9.         /*建立各个节点的出度表*/
  10.         int[] degree = new int[n];
  11.         /*建立图关系，在每个节点的list中存储相连节点*/
  12.         List<List<Integer>> map = new ArrayList<>();
  13.         for (int i = 0; i < n; i++) {
  14.             map.add(new ArrayList<>());
  15.         }
  16.         for (int[] edge : edges) {
  17.             degree[edge[0]]++;
  18.             degree[edge[1]]++;/*出度++*/
  19.             map.get(edge[0]).add(edge[1]);/*添加相邻节点*/
  20.             map.get(edge[1]).add(edge[0]);
  21.         }
  22.         /*建立队列*/
  23.         Queue<Integer> queue = new LinkedList<>();
  24.         /*把所有出度为1的节点，也就是叶子节点入队*/
  25.         for (int i = 0; i < n; i++) {
  26.             if (degree[i] == 1) queue.offer(i);
  27.         }
  28.         /*循环条件当然是经典的不空判断*/
  29.         while (!queue.isEmpty()) {
  30.             res = new ArrayList<>();/*这个地方注意，我们每层循环都要new一个新的结果集合，
  31.             这样最后保存的就是最终的最小高度树了*/
  32.             int size = queue.size();/*这是每一层的节点的数量*/
  33.             for (int i = 0; i < size; i++) {
  34.                 int cur = queue.poll();
  35.                 res.add(cur);/*把当前节点加入结果集，不要有疑问，为什么当前只是叶子节点为什么要加入结果集呢?
  36.                 因为我们每次循环都会新建一个list，所以最后保存的就是最后一个状态下的叶子节点，
  37.                 这也是很多题解里面所说的剪掉叶子节点的部分，你可以想象一下图，每层遍历完，
  38.                 都会把该层（也就是叶子节点层）这一层从队列中移除掉，
  39.                 不就相当于把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图吗*/
  40.                 List<Integer> neighbors = map.get(cur);
  41.                 /*这里就是经典的bfs了，把当前节点的相邻接点都拿出来，
  42.                 * 把它们的出度都减1，因为当前节点已经不存在了，所以，
  43.                 * 它的相邻节点们就有可能变成叶子节点*/
  44.                 for (int neighbor : neighbors) {
  45.                     degree[neighbor]--;
  46.                     if (degree[neighbor] == 1) {
  47.                         /*如果是叶子节点我们就入队*/
  48.                         queue.offer(neighbor);
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         return res;/*返回最后一次保存的list*/
  54.     }
  56. }