310. 最小高度树

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3 

输出: [1]
示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5 

输出: [3, 4]
说明:

根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

本题其实有几个难点，一个是要发现规律，一个是要规律变为代码。
直观上想我们可以用暴力，每个节点都作为根节点来进行一次遍历，然后计算层数取最小值，这样的话定然会超时。
我们就要换种思路，首先发现规律，规律就是，其实这个根节点我们取的是要靠近中间，尽量靠中间的就会是答案。而不是根据节点的邻接点个数来判断。
那如何求出靠中间的呢？我们可以用和https://www.jianshu.com/p/0bb3f89adc82
一样的方法。我们每次都去除掉一个节点为1的节点，留到最后的就是最中心的节点了，如果出现第二张图的结构，就是两个节点都可以取，如果最后只剩下一个，那就是答案。
因此代码与https://www.jianshu.com/p/0bb3f89adc82
也是一致的。
但是总的来说两个难点是需要练习的。
代码如下:

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        
        int [] degrees = new int[n];
        int len = edges.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++){
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < len; i++){
            degrees[edges[i][0]]++;
            degrees[edges[i][1]]++;
            adj.get(edges[i][0]).add(edges[i][1]);
            adj.get(edges[i][1]).add(edges[i][0]);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++){
            if (degrees[i] == 1){
                queue.add(i);
            }
        }
        
        while (n > 2){
            int size = queue.size();
            n -= size;
            for (int i = 0; i < size; i++){
                int j = queue.poll();
                for (int m = 0; m < adj.get(j).size();m++){
                    degrees[adj.get(j).get(m)]--;
                }
                degrees[j] = -1;
            }
            for (int i = 0; i < degrees.length; i++){
                if (degrees[i] == 1){
                    queue.add(i);
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < degrees.length; i++){
            if (degrees[i] >= 0)
                ans.add(i);
        }
        return ans;

     
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-height-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。