###### tags: `Leetcode` `medium` `graph` `python` `c++`

# 310. Minimum Height Trees

## [題目連結:] https://leetcode.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.


## 解題想法:
* 求以哪些點為root時，樹高度最小
* 想法:拓樸排序
* 希望盡可能讓樹高度矮:
* root希望越靠中心越好
* while **從葉節點開始拜訪**
* **一層一層刪除**: degree=1的點
* 刪掉該點與其邊
* ex: Example1: 葉子節點:[0,2,3]，扣掉後，剩下中心結點，即為root(1

* 流程:
* Step1: 建立邊
* Step2:
* res先存目前所有葉節點
* nextLevel=[] 用來紀錄下一層
* Step3: While res
* 對於res中的所有node逐一訪問:
* for neighber in graph[node]:
* 把鄰居連到此node的邊刪除
* 若鄰居degree=1
* 將其加入nextLevel
* 若nextLevel為空即可break
* Step4:
* return res

* 同類型題目:
* [207. Course Schedule](/txZn8rNCReWvEPygWnh-Zg)
* [210. Course Schedule II](/p2vAVMAwRdyn_Wb9O7UZpA)
## Python:

from collections import defaultdict
class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n==1:
            return [0]
        graph=defaultdict(list)
        for u,v in edges:
            #連邊
            graph[u].append(v)
            graph[v].append(u)
        #先刪邊數只有1條的node
        res = [ node for node in range(n) if len(graph[node])==1]
        #收集下一層的
        nextLevel=[]
        while res:
            for node in res:
                for neiber in graph[node]:
                    #把鄰居連到此node的邊刪掉
                    graph[neiber].remove(node)
                    if len(graph[neiber])==1:
                        nextLevel.append(neiber)
            if not nextLevel:
                break
            res=nextLevel #繼續下一輪
            nextLevel=[]  #nextLevel清空
        return res

result = Solution()
n = 3
edges = [[0,1],[0,2]]
ans = result.findMinHeightTrees(n,edges)
print(ans)

## C++:
* 對於list中刪除特定元素
* c++的vector無法像python一樣直接remove
* 改成使用**unordered_set**
* insert()
* erase()

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n==1)
            return {0};
        unordered_map<int,unordered_set<int>> graph;
        for (auto num: edges){
            graph[num[0]].insert(num[1]);
            graph[num[1]].insert(num[0]);
        }
        vector<int> res, nextLevel;
        //collect the leaf node
        for (auto item: graph){
            if (graph[item.first].size()==1)
                res.push_back(item.first);
        }
        //check level
        while (!res.empty()){
            for (auto num: res){
                for (auto neighber: graph[num]){
                    graph[neighber].erase(num);
                    if (graph[neighber].size()==1)
                        nextLevel.push_back(neighber);
                }
            }
            if (nextLevel.empty())
                break;
            res=nextLevel;
            nextLevel.clear();
        }
        return res;
    }
};