解法一：http://siukwan.sinaapp.com/?p=189    https://www.cnblogs.com/TonyYPZhang/p/5123058.html

1.这道题目主要是求一个无向图中，以哪个节点为根节点的树的高度最小；

2.常规方法可以使用BFS或者DFS，对每个点都遍历一遍，求出所有点组成的树的高度，然后找出哪些高度最小的节点，可以通过不断更新最低高度来进行剪枝。实际上我写了BFS和DFS的程序，均出现超时。

3.最终的解题思路采用了不断删除叶子节点，逐渐逼近根节点的方法，在删除叶子节点的同时，会有一些新的节点成为叶子节点，于是继续循环删除，直至不能删除为止，那么剩下的节点就是高度最小的根。

4.当n等于1时，需要特殊处理，直接返回{0}。

5.最终会剩下1个节点或者2个节点，1个节点的情况比较好理解，如{0,1}{0,2}，同时删除了叶子节点1和2，就剩下0；而两个节点的情况为{0,1}，此时0和1的邻居均为1，都是叶子节点，在下一轮操作后，0和1均没有邻居，所以这两个节点都是正确的答class Solution public:

struct TreeNode{        set
     
       list;//使用set结构方便删除邻居        TreeNode(){};        bool isLeaf(){
     return list.size()==1;};//这边的分号不能丢    };//这个分号也不能丢        vector
      
        findMinHeightTrees(int n, vector
       
        
         >& edges) {        if(n==1) return {
     0};                        //使用节点来存储这棵树，耗费的空间为O(n+2e)        vector
         
           tree(n);        for(auto edge:edges){            tree[edge.first].list.insert(edge.second);            tree[edge.second].list.insert(edge.first);        }                vector
          
            node1(0),node2(0);//node1记录当前的叶子节点、node2记录删除node1叶子节点后，成为新的叶子节点的节点 for(int i=0;i
          
         
        
       
      
     

 

另外一种代码：指针得稍微理解一下

class Solution {public:    class TNode{        public:        int val;        unordered_set
      
       neighbours;        TNode(int val):val(val){};        bool isLeaf(){
    return neighbours.size()==1;};    };//加分号        vector
       
         findMinHeightTrees(int n, vector
        
         
          >& edges) {        map
          
            val_nodes;        for(int i=0;i
           
            neighbours.insert(val_nodes[edge.second]); val_nodes[edge.second]->neighbours.insert(val_nodes[edge.first]); } while(val_nodes.size()>2){ list
            
             listq; for(auto it=val_nodes.begin();it!=val_nodes.end();it++){ if(it->second->isLeaf()) listq.push_back(it->second); } for(auto it=listq.begin();it!=listq.end();it++){ TNode* p= *(*it)->neighbours.begin();//it是list的指针，所以要用(*it)转为TNode p->neighbours.erase(*it); (*it)->neighbours.erase(p); val_nodes.erase((*it)->val); } } vector
             
               res; for(auto it=val_nodes.begin();it!=val_nodes.end();it++){ res.push_back(it->first); } return res; }};