欧美高清日韩中文字幕,人妻久操,最新日韩免费在线,日本色视频,久久无人区无码,黄色毛片在线观看,伊人影院在线观看视频,柏欣彤Av色福利一二区

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從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.

樹是一個(gè)無向圖，其中任何兩個(gè)頂點(diǎn)只通過一條路徑連接。換句話說，一個(gè)任何沒有簡單環(huán)路的連通圖都是一棵樹。

給你一棵包含 n 個(gè)節(jié)點(diǎn)的樹，標(biāo)記為 0 到 n - 1 。給定數(shù)字 n 和一個(gè)有 n - 1 條無向邊的 edges 列表（每一個(gè)邊都是一對標(biāo)簽），其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) ai 和 bi 之間存在一條無向邊。

可選擇樹中任何一個(gè)節(jié)點(diǎn)作為根。當(dāng)選擇節(jié)點(diǎn) x 作為根節(jié)點(diǎn)時(shí)，設(shè)結(jié)果樹的高度為 h 。在所有可能的樹中，具有最小高度的樹（即，min(h)）被稱為最小高度樹。

請你找到所有的最小高度樹并按任意順序返回它們的根節(jié)點(diǎn)標(biāo)簽列表。

樹的高度是指根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間最長向下路徑上邊的數(shù)量。

示例

解題

使用廣度優(yōu)先搜索，每次找出只有一個(gè)相鄰結(jié)點(diǎn)的點(diǎn)，既度為1的結(jié)點(diǎn)，作為要?jiǎng)h除的結(jié)點(diǎn)，同時(shí)與這些結(jié)點(diǎn)相連的點(diǎn)的度同時(shí)減1，當(dāng)減一后的結(jié)點(diǎn)的度也變成了1，則作為新的要?jiǎng)h除的結(jié)點(diǎn)，壓入到隊(duì)列中。具體實(shí)現(xiàn)過程，看代碼，都有詳細(xì)注釋了。

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);
         //統(tǒng)計(jì)各個(gè)結(jié)點(diǎn)的入度，這里是無向圖，實(shí)際既相鄰的結(jié)點(diǎn)的數(shù)量
         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;//隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索
         //將起始的度為1的結(jié)點(diǎn)壓入到隊(duì)列中
         for(int i=0;i<n;++i){
             if(in_degree[i]==1){
                 q.push(i);
                 in_degree[i]=0;//標(biāo)識不再訪問，變相的刪除結(jié)點(diǎn)操作
             }
         }
    //當(dāng)沒有遍歷的結(jié)點(diǎn)的數(shù)量小于等于2時(shí)，則終止循環(huán)，剩余的這1個(gè)或2個(gè)結(jié)點(diǎn)，即為中間結(jié)點(diǎn)
         while(n>2){
             int cur_size=q.size();//當(dāng)前層要?jiǎng)h除的結(jié)點(diǎn)數(shù)量
             n-=cur_size;//刪除結(jié)點(diǎn)
             //逐個(gè)遍歷要?jiǎng)h除的結(jié)點(diǎn)，減少相鄰的結(jié)點(diǎn)的度
             while(cur_size--){
                int cur_index=q.front();//當(dāng)前結(jié)點(diǎn)
                q.pop();
                //遍歷當(dāng)前結(jié)點(diǎn)的相鄰結(jié)點(diǎn)，再相鄰結(jié)點(diǎn)沒有被刪除過的情形下，既度符合要求的情形下
                for(int& cur_i:graph[cur_index]){
                    if(in_degree[cur_i]>1){//度符合要求，則可以訪問
                      //該相鄰結(jié)點(diǎn)的度減1
                         --in_degree[cur_i];
                         //若度等于1，則說明也是新的葉子結(jié)點(diǎn)，既可以刪除的結(jié)點(diǎn)，壓入到隊(duì)列中，并將對應(yīng)的度置為0進(jìn)行標(biāo)識
                         if(in_degree[cur_i]==1){
                            q.push(cur_i);
                            in_degree[cur_i]=0;
                        }
                    }
                }
             }
         }
         //獲得結(jié)果
         vector<int> res;
         while(!q.empty()){
             res.push_back(q.front());
             q.pop();
         }
         return res;
    }
};