LeetCode刷题实战310：最小高度树 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最小高度树，我们先来看题面：

https://leetcode-cn.com/problems/minimum-height-trees/

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为最小高度树。

请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例

解题

使用广度优先搜索，每次找出只有一个相邻结点的点，既度为1的结点，作为要删除的结点，同时与这些结点相连的点的度同时减1，当减一后的结点的度也变成了1，则作为新的要删除的结点，压入到队列中。具体实现过程，看代码，都有详细注释了。

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
      //处理特殊的情形
        if(n==1){
            return {0};
        }
        if(n==2){
            return {0,1};
        }
        //建立图
         vector<vector<int>> graph(n);
         //统计各个结点的入度，这里是无向图，实际既相邻的结点的数量
         vector<int> in_degree(n,0);
         for(vector<int>& edge:edges){
             graph[edge[0]].push_back(edge[1]);
             graph[edge[1]].push_back(edge[0]);
             ++in_degree[edge[0]];
             ++in_degree[edge[1]];
         }
         queue<int> q;//队列实现广度优先搜索
         //将起始的度为1的结点压入到队列中
         for(int i=0;i<n;++i){
             if(in_degree[i]==1){
                 q.push(i);
                 in_degree[i]=0;//标识不再访问，变相的删除结点操作
             }
         }
    //当没有遍历的结点的数量小于等于2时，则终止循环，剩余的这1个或2个结点，即为中间结点
         while(n>2){
             int cur_size=q.size();//当前层要删除的结点数量
             n-=cur_size;//删除结点
             //逐个遍历要删除的结点，减少相邻的结点的度
             while(cur_size--){
                int cur_index=q.front();//当前结点
                q.pop();
                //遍历当前结点的相邻结点，再相邻结点没有被删除过的情形下，既度符合要求的情形下
                for(int& cur_i:graph[cur_index]){
                    if(in_degree[cur_i]>1){//度符合要求，则可以访问
                      //该相邻结点的度减1
                         --in_degree[cur_i];
                         //若度等于1，则说明也是新的叶子结点，既可以删除的结点，压入到队列中，并将对应的度置为0进行标识
                         if(in_degree[cur_i]==1){
                            q.push(cur_i);
                            in_degree[cur_i]=0;
                        }
                    }
                }
             }
         }
         //获得结果
         vector<int> res;
         while(!q.empty()){
             res.push_back(q.front());
             q.pop();
         }
         return res;
    }
};