310. Minimum Height Trees -------------M ！！！！！！！！

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Note:

(1) According to the definition of tree on Wikipedia: “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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

A:

Longest Path

It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree.
Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).

Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs).
The following is some thought of the latter.

Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.
Then y must be one of the endpoints on some longest path.
Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.

Now, the path from y to z is the longest one, and thus its middle point(s) is the answer. 

Tree DP

Alternatively, one can solve this problem directly by tree dp.
Let dp[i] be the height of the tree when the tree root is i.
We compute dp[0] ... dp[n - 1] by tree dp in a dfs manner.

Arbitrarily pick a node, say node 0, as the root, and do a dfs.
When we reach a node u, and let T be the subtree by removing all u's descendant (see the right figure below).
We maintain a variable acc that keeps track of the length of the longest path in T with one endpoint being u.
Then dp[u] = max(height[u], acc)
Note, acc is 0 for the root of the tree.

             |                 |
             .                 .
            /|\               /|\
           * u *             * u *
            /|\
           / | \
          *  v  *

. denotes a single node, and * denotes a subtree (possibly empty).

Now it remains to calculate the new acc for any of u's child, v.
It is easy to see that the new acc is the max of the following

1. acc + 1 --- extend the previous path by edge uv;

2. max(height[v'] + 2), where v != v' --- see below for an example.

            u
           /|
          / |
         v' v
         |
         .
         .
         .
         |
         .
   

In fact, the second case can be computed in O(1) time instead of spending a time proportional to the degree of u.
Otherwise, the runtime can be quadratic when the degree of some node is Omega(n).
The trick here is to maintain two heights of each node, the largest height (the conventional height), and the second largest height
(the height of the node after removing the branch w.r.t. the largest height).

Therefore, after the dfs, all dp[i]'s are computed, and the problem can be answered trivially.
The total runtime is still O(n). Java Solution

 /*
    *剥洋葱解法：从外层向里层进行BFS遍历
    *具体思路：
    *将图转化为邻接表存储后，若只有一条边的则为最外围的元素，将外围元素全部加入队列
    *然后在队列弹出时，需要将这个结点在邻接表中删除，层层向里，最后只剩下2个元素以内时，则为最中心元素，即以它们作为树根会得到最小高度树
    */

这个在VS里是能通过的。 可是在LC中，（例如第一个例子） map第一遍的时候，就空了。而VS中还有一个值

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        // idea : peel the onion, until the valid 
        unordered_map<int,unordered_set<int>> map;
        for (auto edge : edges) {
            int a = edge[0], b = edge[1];
            map[a].insert(b);
            map[b].insert(a);
        }
        vector<int> res;
        while (true) {
            auto copy = map;
            auto iter = map.begin();
            while (iter != map.end()) {
                if (iter->second.size() <= 1) { // must be <=1, as exist no edges
                    int a = iter->first;
                    if (iter->second.size() == 1) {
                        auto anotherEnd = *(iter->second.begin());
                        map[anotherEnd].erase(a);
                    }
                    iter = map.erase(iter);
                }
                else {
                    iter++;
                }
            }
            if (map.size() == 0) { // then nodes before this round, would be ansers
                iter = copy.begin();
                while (iter != copy.end()) {
                    res.push_back(iter->first);
                    iter++;
                }
                break;
            }
        }
        return res; // shall not hit
    }
};

Mistakes：