Leetcode 310 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 indicates that there is an undirected edge between the two nodes and 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.

Example 1:

image.png

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

image.png

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Example 3:

Input: n = 1, edges = []
Output: [0]

Example 4:

Input: n = 2, edges = [[0,1]]
Output: [0,1]

Constraints:

• 
• 
• 
• 
• All the pairs (, ) are distinct.
  The given input is guaranteed to be a tree and there will be no repeated edges.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-height-trees

思路：

首先用bfs或者dfs求树高度是很好求的，但是将每一个节点尝试做根节点，每个都求一边复杂度较高，据说会超时。

因此，这个题目采用的是一个比较灵活的BFS方法，即从叶子节点开始BFS，像剥洋葱一样先把最外层的度数为1的叶子节点剥去，获得一个新的树，再剥下一层，直到剥完，那么剥完之前的最后一层即为所求。

在实现的时候需要注意的细节是“剥”的操作对应degree数组相应节点的度数减少。因为一个edge连接两条边，在剥的时候graph是不变的，只是degree数组变化，删掉一条边相当于减去两个节点的1个度数，但是这条边会被两个节点各访问一次，因此在一个节点的访问中只将除了此节点之外的相邻节点作度数减少，自己的度数让别人来减。

代码如下：

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1)return vector<int>({0});
        vector<int> degree(n,0);
        vector<vector<int>> graph(n,vector<int>());
        for(auto edge: edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        queue<int> q;
        vector<int> ans;
        for(int i=0;i<degree.size();i++){
            if(degree[i]==1){
                q.push(i);
            }
        }
        while(!q.empty()){
            int size=q.size();
            ans.clear();
            for(int i=0;i<size;i++){
                int front=q.front();
                q.pop();
                ans.push_back(front);
                for(auto node:graph[front]){
                    degree[node]--;
                    if(degree[node]==1)q.push(node);
                }
            }   
        }
        return ans;
    }
};