## Thursday, November 26, 2015

### Leetcode 310 - Minimum Height Trees

leetcode Minimum Height Trees - 细语呢喃
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]`
Hint:
1. How many MHTs can a graph have at most?
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.
http://algobox.org/minimum-height-trees/
Our problem want us to find the minimum height trees and return their root labels. First we can think about a simple case — a path graph.
For a path graph of n nodes, find the minimum height trees is trivial. Just designate the middle point(s) as roots.
Despite its triviality, let design a algorithm to find them.
Suppose we don’t know n, nor do we have random access of the nodes. We have to traversal. It is very easy to get the idea of two pointers. One from each end and move at the same speed. When they meet or they are one step away, (depends on the parity of `n`), we have the roots we want.
This gives us a lot of useful ideas to crack our real problem.
For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.
It is easy to see that the last two pointers are from the two ends of the longest path in the graph.
The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What’s left is our answer!
The time complexity and space complexity are both `O(n)`.
Note that for a tree we always have `V` = `n``E` = `n-1`
Using `List` is faster than my solution using `HashMap`.
Whenever the Direct Access Table is possible I usually avoid Hash Table. It it better both in time and space.

``````public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);

for (int[] edge : edges) {
}

List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; ++i)

while (n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int i : leaves) {
}
leaves = newLeaves;
}
return leaves;
}``````
http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html
1. Note in the implementation, we use List<Set<Integer>> to represent a adj list. That is because the vertex Id ranges from 0 to n - 1, we can use the list index to represent the vertex Id.
2. In the implementation, we don't really delete the leaf nodes, which will result in an O(n) time since the adjList is a list. Instead, we find the leaf nodes in each iteration and remove it in the neighbor list. Then we find out the new leaf nodes.
`    ``public` `List<Integer> findMinHeightTrees(``int` `n, ``int``[][] edges) {`
`        ``List<Integer> result = ``new` `ArrayList<>();`
`        ``if` `(n <= ``0``) {`
`            ``return` `result;`
`        ``}`
`        `
`        ``// Corner case: there is a single node and no edge at all`
`        ``if` `(n == ``1` `&& edges.length == ``0``) {`
`            ``result.add(``0``);`
`            ``return` `result;`
`        ``}`
`        `
`        ``// Step 1: construct the graph`
`        ``List<Set<Integer>> adjList = ``new` `ArrayList<>();`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``adjList.add(``new` `HashSet<>());`
`        ``}`
`        `
`        ``for` `(``int``[] edge : edges) {`
`            ``int` `from = edge[``0``];`
`            ``int` `to = edge[``1``];`
`            ``adjList.get(from).add(to);`
`            ``adjList.get(to).add(from);`
`        ``}`
`        ``// Remove leaf nodes`
`        ``List<Integer> leaves = ``new` `ArrayList<>();`
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``if` `(adjList.get(i).size() == ``1``) {`
`                ``leaves.add(i);`
`            ``}`
`        ``}`
`        ``while` `(n > ``2``) {`
`            ``// identify and remove all leaf nodes`
`            ``n -= leaves.size();`
`            ``List<Integer> newLeaves = ``new` `ArrayList<>();`
`            ``for` `(``int` `leaf : leaves) {`
`                ``int` `neighbor = adjList.get(leaf).iterator().next();`
`                ``adjList.get(neighbor).remove(leaf);`
`                `
`                ``if` `(adjList.get(neighbor).size() == ``1``) {`
`                    ``newLeaves.add(neighbor);`
`                ``}`
`            ``}`
`            `
`            ``leaves = newLeaves;`
`        ``}`
`        `
`        ``return` `leaves;`
`    ``}`
http://www.cnblogs.com/grandyang/p/5000291.html

```    vector<int> findMinHeightTrees(int n, vector<pair<int, int> >& edges) {
if (n == 1) return {0};
vector<int> res, d(n, 0);
vector<vector<int> > g(n, vector<int>());
queue<int> q;
for (auto a : edges) {
g[a.first].push_back(a.second);
++d[a.first];
g[a.second].push_back(a.first);
++d[a.second];
}
for (int i = 0; i < n; ++i) {
if (d[i] == 1) q.push(i);
}
while (n > 2) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
int t = q.front(); q.pop();
--n;
for (int i : g[t]) {
--d[i];
if (d[i] == 1) q.push(i);
}
}
}
while (!q.empty()) {
res.push_back(q.front()); q.pop();
}
return res;
}```

def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if n==1: return [0]
digree = [0 for i in xrange(n)]
g = [[] for i in xrange(n)]
for x,y in edges:
digree[x] += 1
digree[y] += 1
g[y].append(x)
leaves = [i for i in xrange(n) if digree[i]==1]
nodes = n
while nodes > 2:
temp = []
for i in leaves:
digree[i] = 0
nodes -= 1
for j in g[i]:
digree[j] -= 1
if digree[j] == 1:
temp.append(j)
leaves = temp
return leaves
def findMinHeightTrees(self, n, edges): """ :type n: int :type edges: List[List[int]] :rtype: List[int] """ children = collections.defaultdict(set) for e in edges: children[e[0]].add(e[1]) children[e[1]].add(e[0]) vertices = set(children.keys()) while len(vertices) > 2: leaves = [x for x in children if len(children[x]) == 1] // previous solution better for x in leaves: for y in children[x]: children[y].remove(x) del children[x] vertices.remove(x) return list(vertices) if n != 1 else [0]
It's easy to know there are most two nodes to return, which are the medium nodes in the longest path in the tree. level travels, remove the leafs level by level
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
//check for the single node situation
if (n < 2) {
return queue;
}
//initiate map, indegree, and queue
int count = n;
int[] indegree = new int[n];
Map<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
for (int i = 0; i < count; i++) {
map.put(i, new HashSet<Integer>());
}
for (int[] edge: edges) {
indegree[edge[0]]++;
indegree[edge[1]]++;
}
for (int i = 0; i < count; i++){
if (indegree[i] == 1)
}
//check from the outer layer to inner layer, stop when count == 1 or 2
//which means we arrive at the center
while (count > 2) {
for (int cur: queue) {
count--;
for (int next: map.get(cur)) {
map.get(next).remove(cur);
if (--indegree[next] == 1)
}
}
queue = newqueue;
}
return queue;

}
https://leetcode.com/discuss/71738/easiest-75-ms-java-solution
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<>();
if(n <= 1) {leaves.add(0); return leaves;}

Map<Integer, Set<Integer>> graph = new HashMap<>();   // use list<set<>>
for(int i = 0; i < n; i++) graph.put(i, new HashSet<Integer>());
for(int[] e : edges) {
}

// Add leaves which have one leaf
for(int i = 0; i < n; i++) {
}

// Remove leaves level by level
while(n > 2) {
List<Integer> newLeaves = new ArrayList<>();
for(int leaf : leaves) {
for(int nb : graph.get(leaf)) {
// Remove connection
graph.get(leaf).remove(nb);
graph.get(nb).remove(leaf);
n--;
if(graph.get(nb).size() == 1) {
}
}
}
leaves = newLeaves;
}
return leaves;
}
X. TODO
https://discuss.leetcode.com/topic/30956/two-o-n-solutions
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.

• 做两次树遍历
首先任意选取树的一个结点x作为遍历开始的根结点，然后利用BFS或DFS找到距离x最远的结点y。y一定位于某一条最大距离的一端。然后以y作为遍历开始的根结点，执行另一次BFS或DFS，找到距离y最远的结点z。那么从y到z的所构成的最远路径的中点就是我们需要寻找的MHT的根。
https://nb4799.neu.edu/wordpress/?p=1996
 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 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 == 0: return []         if n == 1: return [0]                   res = []         adj = defaultdict(set)           for e in edges:            adj[e[0]].add(e[1])            adj[e[1]].add(e[0])           max_path = self.maxpath(adj, edges[0][0], None)             max_path = self.maxpath(adj, max_path[-1], None)                 l = len(max_path)           if l % 2 == 0:             return max_path[l/2-1:l/2+1]         else:             return max_path[l/2:l/2+1]               def maxpath(self, adj, cur_node, prev_node):         max_path = [cur_node]            for n in adj[cur_node]:             # check whether the next visiting node is not visited before.             # use the property that tree has no cycle. just need to check with last visited node.             if n != prev_node:                 new_max_path = [cur_node] + self.maxpath(adj, n, cur_node)                     if len(max_path) < len(new_max_path):                     max_path = new_max_path           return max_path
https://discuss.leetcode.com/topic/30588/solution-share-midpoint-of-longest-path
1. G = <V[1..n], E[1..n-1]>, G is connected;
2. Find a path P = V[p[1]], V[p[2]], ... V[p[l]] which is the longest path in G
3. The Midpoint of the path V[p[floor(l/2)]], or, V[p[ceil(l/2)]] is the answer
``````    # longest path from node i
def longestPath(self, n, e, i):
a, b = set([i]), [[i, 0]]
r = list(range(n))
while len(b):
t, d = b.pop(0)
for j in e[t]:
if j in a: continue
b.append([j, d + 1])
r[j] = t
p = [t]
while p[0] != i:
p.insert(0, r[p[0]])
return p

def findMinHeightTrees(self, n, edges):
e = [[] for i in range(n)]
for x, y in edges:
e[x].append(y)
e[y].append(x)
p = self.longestPath(n, e, 0)
q = self.longestPath(n, e, p[-1])
return list(sorted(q[(len(q)-1)//2:len(q)//2+1]))``````
http://www.cnblogs.com/yrbbest/p/5060225.html

Time Complexity - O(n2)， Space Complexity - O(n)           <-  TLE
```    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
if (edges == null || edges.length == 0 || edges.length != n - 1) return res;
List<LinkedList<Integer>> paths = new ArrayList<>();    // no cycle, no duplicate
int len = 0, maxIndex = 0;
for (int[] edge : edges) {
for (int i = 0; i < paths.size(); i++) {
else if (path.peekFirst() == edge[1]) path.addFirst(edge[0]);
else if (path.peekLast() == edge[0]) path.addLast(edge[1]);
else if (path.peekLast() == edge[1]) path.addLast(edge[0]);

if (paths.get(i).size() > len) {
len = paths.get(i).size();
maxIndex = i;
}
}
}

if (longestPath.size() % 2 == 0) {
} else {
}
return res;
}```
https://github.com/lydxlx1/LeetCode/blob/master/src/_310.java
int n;
List<Integer>[] e;

private void bfs(int start, int[] dist, int[] pre) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<>();
dist[start] = 0;
visited[start] = true;
pre[start] = -1;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : e[u])
if (!visited[v]) {
visited[v] = true;
dist[v] = dist[u] + 1;
pre[v] = u;
}
}
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n <= 0) return new ArrayList<>();
this.n = n;
e = new List[n];
for (int i = 0; i < n; i++)
e[i] = new ArrayList<>();
for (int[] pair : edges) {
int u = pair[0];
int v = pair[1];
}

int[] d1 = new int[n];
int[] d2 = new int[n];
int[] pre = new int[n];
bfs(0, d1, pre);
int u = 0;
for (int i = 0; i < n; i++)
if (d1[i] > d1[u]) u = i;

bfs(u, d2, pre);
int v = 0;
for (int i = 0; i < n; i++)
if (d2[i] > d2[v]) v = i;

List<Integer> list = new ArrayList<>();
while (v != -1) {
v = pre[v];
}

if (list.size() % 2 == 1) return Arrays.asList(list.get(list.size() / 2));
else return Arrays.asList(list.get(list.size() / 2 - 1), list.get(list.size() / 2));
}

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.
http://blog.csdn.net/yaokai_assultmaster/article/details/52051181
• 利用数组`dp[i]`储存以i作为根结点时的树的高度。利用DFS和动态规划的思路来计算`dp[0]``dp[n-1]`。
任意选取一个结点作为根结点开始DFS，例如0。
当我们到达一个结点u的时候，利用T来表示去掉u的子树后余下的树。利用`height[]`来表示u的高度，使用变量`acc`记录去掉u的子树后树T中以u作为结束结点的最长路径的长度（既u的深度）。那么显然`dp[u] = max{acc, height[u]}`。acc对于根结点来说是0。
``````             |                |
.                .
/|\              /|\
* u *            * u *
/|\
/ | \
*  v  *```
1
2
3
4
5
6
7

1
2
3
4
5
6
7

```
.表示单独结点，*表示子树。

1. acc+1 直接将u点的acc长度向uv延伸1
2. max(height[v’]+2) v’是u的子结点且v’ != v。如下图所示
``````             u
/|
/ |
v' v
|
.
.
.
|
.```
1
2
3
4
5
6
7
8
9
10

1
2
3
4
5
6
7
8
9
10

```

* 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 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 the 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). */ if (n <= 0) return new ArrayList<>(); if (n == 1) return Arrays.asList(0); int[] height1 = new int[n]; //stores the largest height of a node int[] height2 = new int[n]; //stores the second largest height of a node int[] dp = new int[n]; List<Integer>[] tree = new List[n]; for (int i = 0; i < n; i++) { tree[i] = new ArrayList<>(); } for (int[] edge : edges) { tree[edge[0]].add(edge[1]); tree[edge[1]].add(edge[0]); } dfs(0, -1, height1, height2, tree); dfs(0, -1, 0, height1, height2, dp, tree); int min = dp[0]; for (int i = 0; i < n; i++) { if (dp[i] < min) { min = dp[i]; } } List<Integer> result = new ArrayList<>(); for (int i = 0; i < n; i++) { if (dp[i] == min) { result.add(i); } } return result; } private void dfs(int node, int parent, int[] height1, int[] height2, List<Integer>[] tree) { height1[node] = Integer.MIN_VALUE; height2[node] = Integer.MIN_VALUE; for (int child : tree[node]) { if (child != parent) { dfs(child, node, height1, height2, tree); int tmpheight = height1[child] + 1; if (tmpheight > height1[node]) { height2[node] = height1[node]; height1[node] = tmpheight; } else if(tmpheight > height2[node]) { height2[node] = tmpheight; } } } height1[node] = Math.max(height1[node], 0); } private void dfs(int node, int parent, int acc, int[] height1, int[] height2, int[] dp, List<Integer>[] tree) { dp[node] = Math.max(acc, height1[node]); for (int child : tree[node]) { if (child != parent) { int newAcc = Math.max(acc + 1, height1[child] + 1 == height1[node] ? height2[node] + 1 : height1[node] + 1); dfs(child, node, newAcc, height1, height2, dp, tree); } } }
http://www.cnblogs.com/TonyYPZhang/p/5123058.html

1. 视某个节点为树根节点，求这棵树的树高。
2. 对所有节点进行上面的求解，得到 n 个树高，其中高度最小的树的树根即为原题目的解。

height(A) = max(height(A.next0), height(A.next2),... height(A.nextk)) + 1

```4     map<string, int> direc_height;
5
6 public:
7
8     /**
9      * calulate the height of a tree which parent node is p and current node is node
10      *
11      */
12     int getHeight(gnode* node, gnode* p){
13         int h = 0;
14         for (int i = 0; i < node->neighbours.size(); i++){
15             gnode* tmpn = node->neighbours[i];
16             if (tmpn == p){
17                 continue;
18             }
19
20             int tmph;
21             string str = to_string(node->val) + "_" + to_string(tmpn->val);
22             if(direc_height.count(str) != 0){
23                 tmph = direc_height[str];
24             }else{
25                 tmph = getHeight(tmpn, node);
26                 direc_height[str] = tmph;
27             }
28
29             h = max(h, tmph);
30         }
31
32         return h + 1;
33     }
34
35     vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
36
37         map<int, gnode*> val_node;
38         for(int i = 0; i < n ; i++){
39             gnode* node = new gnode(i);
40             val_node[i] = node;
41         }
42
43         for (int i = 0; i < edges.size(); i++){
44             pair<int, int> pp = edges[i];
45             val_node[pp.first]->neighbours.push_back(val_node[pp.second]);
46             val_node[pp.second]->neighbours.push_back(val_node[pp.first]);
47         }
48
49         int minh = INT_MAX;
50
51         map<int, int> node_height;
52
53         map<int, gnode*>::iterator m_iter;
54         for(m_iter = val_node.begin(); m_iter != val_node.end(); m_iter++){
55             int h = getHeight(m_iter->second, NULL);
56             node_height[m_iter->first] = h;
57             minh = min(minh, h);
58         }
59
60         vector<int> res;
61         map<int, int>::iterator mii_iter;
62         for(mii_iter = node_height.begin(); mii_iter != node_height.end(); mii_iter++){
63             if(mii_iter->second == minh){
64                 res.push_back(mii_iter->first);
65             }
66         }
67
68         return res;
69     }```
int n;
List<Integer>[] e;
int[] height1;
int[] height2;
int[] dp;

private void dfs(int u, int parent) {
height1[u] = height2[u] = -Integer.MIN_VALUE / 10;
for (int v : e[u])
if (v != parent) {
dfs(v, u);
int tmp = height1[v] + 1;
if (tmp > height1[u]) {
height2[u] = height1[u];
height1[u] = tmp;
} else if (tmp > height2[u]) {
height2[u] = tmp;
}
}
height1[u] = Math.max(height1[u], 0); // in case u is a leaf.
}

private void dfs(int u, int parent, int acc) {
dp[u] = Math.max(height1[u], acc);
for (int v : e[u])
if (v != parent) {
int newAcc = Math.max(acc + 1, (height1[v] + 1 == height1[u] ? height2[u] : height1[u]) + 1);
dfs(v, u, newAcc);
}
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n <= 0) return new ArrayList<>();
if (n == 1) return Arrays.asList(0);

this.n = n;
e = new List[n];
for (int i = 0; i < n; i++)
e[i] = new ArrayList<>();
for (int[] pair : edges) {
int u = pair[0];
int v = pair[1];
}

height1 = new int[n];
height2 = new int[n];
dp = new int[n];

dfs(0, -1);
dfs(0, -1, 0);

int min = dp[0];
for (int i : dp)
if (i < min) min = i;

List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++)
return ans;
}
https://apolloydy.wordpress.com/2015/11/26/minimum-height-trees/
1 Find the longest path in the tree, start from node T1 to node T2; (first bfs find T1 and the second bfs find T2 and remember the parent path. O(n))

2 Find the middle node/nodes for T2 to T1 (Get from parent path, need to take care of odd even cases, O(n))

`    ``vector<``int``> findMinHeightTrees(``int` `n, vector<pair<``int``, ``int``>>& edges) {`
`        ``vector<``int``> res;`
`        ``if` `(n<=0) {`
`            ``return` `res;`
`        ``}`
`        ``if` `(n==1) {`
`            ``res.push_back(0);`
`            ``return` `res;`
`        ``}`
`        ``vector<unordered_set<``int``>> G(n);`
`        ``for` `(``const` `pair<``int``,``int``> &edge: edges) {`
`            ``G[edge.first].insert(edge.second);`
`            ``G[edge.second].insert(edge.first);`
`        ``}`
`        ``queue<``int``> Q;`
`        ``for` `(``int` `i=0; i<n; ++i) {`
`            ``// n>0 all tree node must have a degree >= 1;`
`            ``if` `(G[i].size() ==1) {`
`                ``Q.push(i);`
`            ``}`
`        ``}`
`        ``int` `remain = n;`
`        ``while` `(remain>2) {`
`            ``int` `size = Q.size();`
`            ``remain -= size;`
`            ``for` `(``int` `j = 0; j<size; ++j) {`
`                ``// Q should never be zero for a valid tree input;`
`                ``int` `cur = Q.front();`
`                ``Q.pop();`
`                ``for` `(``const` `int` `&next : G[cur]) {`
`                    ``G[next].erase(cur);`
`                    ``if` `(G[next].size() == 1) {`
`                        ``Q.push(next);`
`                    ``}`
`                ``}`
`            ``}`
`        ``}`
`        ``while` `(!Q.empty()) {`
`            ``res.push_back(Q.front());`
`            ``Q.pop();`
`        ``}`
`        ``return` `res;`
`    ``}`

def findMinHeightTrees(self, n, edges):
INF = 0x7ffffffe
dis = [[INF for j in xrange(n)] for i in xrange(n)]
for i in xrange(n): dis[i][i] = 0
g = [[0 for j in xrange(n)] for i in xrange(n)]
for x,y in edges:
g[x][y] = g[y][x] = 1
for x,y in edges:
dis[x][y] = dis[y][x] = 1
for i in xrange(n):
dis[y][i] = dis[i][y] = min(dis[i][y], dis[i][x] + 1)
dis[x][i] = dis[i][x] = min(dis[i][x], dis[i][y] + 1)
res  = []
min_dis = INF
for i in xrange(n):
temp = max(dis[i])
if temp < min_dis:
res = []
res.append(i)
min_dis = temp
elif temp == min_dis:
res.append(i)
return res
http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html
A brute-force solution is we can construct the graph first, then for each vertex as a root of the tree, we calculate the height, and then compare the height with the minimum height we got so far. Update the minimum if necessary. Since getting the height of a tree takes O(n) time, and we need to traverse each vertex of the graph, the total time complexity is O(n^2).
`    ``public` `List<Integer> findMinHeightTrees(``int` `n, ``int``[][] edges) {`
`        ``List<Integer> result = ``new` `ArrayList<>();`
`        ``if` `(n <= ``0` `|| edges == ``null` `|| edges.length == ``0``) {`
`            ``return` `result;`
`        ``}`
`        `
`        ``// Step 1: construct the adjList`
`        ``Map<Integer, List<Integer>> adjList = ``new` `HashMap<>();`
`        `
`        ``for` `(``int``[] edge : edges) {`
`            ``// add forward edge`
`            ``int` `from = edge[``0``];`
`            ``int` `to = edge[``1``];`
`            `
`            ``if` `(!adjList.containsKey(from)) {`
`                ``List<Integer> neighbors = ``new` `ArrayList<>();`
`                ``neighbors.add(to);`
`                ``adjList.put(from, neighbors); `
`            ``} ``else` `{`
`                ``List<Integer> neighbors = adjList.get(from);`
`                ``neighbors.add(to);`
`                ``adjList.put(from, neighbors);`
`            ``}`
`            `
`            ``// Add the reverse edge`
`            ``if` `(!adjList.containsKey(to)) {`
`                ``List<Integer> neighbors = ``new` `ArrayList<>();`
`                ``neighbors.add(from);`
`                ``adjList.put(to, neighbors);`
`            ``} ``else` `{`
`                ``List<Integer> neighbors = adjList.get(to);`
`                ``neighbors.add(from);`
`                ``adjList.put(to, neighbors);`
`            ``}`
`        ``}`
`        `
`        ``// Step 2: iterate each vertex as the root and get the height`
`        ``boolean``[] visited = ``new` `boolean``[n];`
`        ``int` `minHeight = Integer.MAX_VALUE;`
`        `
`        ``for` `(``int` `i = ``0``; i < n; i++) {`
`            ``int` `height = getHeightOfTree(i, adjList, visited);`
`            ``if` `(height < minHeight) {`
`                ``result.clear();`
`                ``result.add(i);`
`                ``minHeight = height;`
`            ``} ``else` `if` `(height == minHeight) {`
`                ``result.add(i);`
`            ``}`
`        ``}`
`        `
`        ``return` `result;`
`    ``}`
`    `
`    ``private` `int` `getHeightOfTree(``int` `root, Map<Integer, List<Integer>> adjList, `
`                                ``boolean``[] visited) {`
`        ``List<Integer> neighbors = adjList.get(root);`
`        ``visited[root] = ``true``;`
`        `
`        ``int` `maxHeight = ``0``;`
`        `
`        ``for` `(Integer neighbor : neighbors) {`
`            ``if` `(!visited[neighbor]) {`
`                ``maxHeight = Math.max(maxHeight, `
`                  ``getHeightOfTree(neighbor, adjList, visited));`
`            ``}`
`        ``}`
`        `
`        ``visited[root] = ``false``;`
`        `
`        ``return` `maxHeight + ``1``;`
`    ``}`
http://blog.csdn.net/yaokai_assultmaster/article/details/52051181