图相关题目

1. Minimum Height Trees
   For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

思路：剥洋葱法。我们需要建立一个图g，是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。我们开始将所有只有一个连接边的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，并且在其相连节点的集合中将该叶节点删去，如果删完后此节点也也变成一个叶节点了，加入队列中，再下一轮删除。那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点啦

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        
        List<Integer> res = new ArrayList<>();
        if(n==1){
            res = new ArrayList<Integer>();
            res.add(0);
            return res;
        }
        
        // 声明+初始化
        List<List<Integer>>  graph = new ArrayList<List<Integer>>(); // 图的二位矩阵表示发 
        int[] indegree = new int[n]; // 节点的入度
        for(int i=0;i<n;i++){
            List<Integer> cur_level = new ArrayList<Integer>();
            graph.add(cur_level);
        }
        
        // 填充图数据
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int[] edge: edges){
            int inNode=edge[0];
            int outNode=edge[1];
            
            // 图矩阵
            graph.get(inNode).add(outNode);
            graph.get(outNode).add(inNode);
            // 入度节点矩阵
            indegree[inNode]++;
            indegree[outNode]++;
        }
        
        // 初始化queue： 获取当前最外层的叶子节点
        for(int i=0;i<n;i++){
            if(indegree[i]==1)
                queue.offer(i);
        }
        
        while(!queue.isEmpty()){
            int size = queue.size();
            res=new ArrayList<Integer>();
            
            // 遍历当前叶子节点
            for(int i=0;i<size;i++){
                int cur_leaf = queue.poll();
                indegree[cur_leaf]--;
                res.add(cur_leaf);
                
                // 获取当前叶子节点的根节点,将根节点的入度也-1
                for(int root: graph.get(cur_leaf)){
                    indegree[root]--;
                    if(indegree[root] ==1)
                        queue.offer(root);
                }
            }
        }
        return res;
    }
}