抄個(gè)題目先：

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.

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-height-trees

思路：

首先用bfs或者dfs求樹高度是很好求的，但是將每一個(gè)節(jié)點(diǎn)嘗試做根節(jié)點(diǎn)，每個(gè)都求一邊復(fù)雜度較高，據(jù)說(shuō)會(huì)超時(shí)。

因此，這個(gè)題目采用的是一個(gè)比較靈活的BFS方法，即從葉子節(jié)點(diǎn)開始BFS，像剝洋蔥一樣先把最外層的度數(shù)為1的葉子節(jié)點(diǎn)剝?nèi)?，獲得一個(gè)新的樹，再剝下一層，直到剝完，那么剝完之前的最后一層即為所求。

在實(shí)現(xiàn)的時(shí)候需要注意的細(xì)節(jié)是“剝”的操作對(duì)應(yīng)degree數(shù)組相應(yīng)節(jié)點(diǎn)的度數(shù)減少。因?yàn)橐粋€(gè)edge連接兩條邊，在剝的時(shí)候graph是不變的，只是degree數(shù)組變化，刪掉一條邊相當(dāng)于減去兩個(gè)節(jié)點(diǎn)的1個(gè)度數(shù)，但是這條邊會(huì)被兩個(gè)節(jié)點(diǎn)各訪問(wèn)一次，因此在一個(gè)節(jié)點(diǎn)的訪問(wèn)中只將除了此節(jié)點(diǎn)之外的相鄰節(jié)點(diǎn)作度數(shù)減少，自己的度數(shù)讓別人來(lái)減。

代碼如下：

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;
    }
};