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
You can assume that no duplicate edges will appear in
Whenever the Direct Access Table is possible I usually avoid Hash Table. It it better both in time and space.
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.
http://www.cnblogs.com/grandyang/p/5000291.html
这道题虽然是树的题目，但是跟其最接近的题目是Course Schedule 课程清单和Course Schedule II 课程清单之二。由于LeetCode中的树的题目主要都是针对于二叉树的，而这道题虽说是树但其实本质是想考察图的知识，这道题刚开始在拿到的时候，我最先想到的解法是遍历的点，以每个点都当做根节点，算出高度，然后找出最小的，但是一时半会又写不出程序来，于是上网看看大家的解法，发现大家推崇的方法是一个类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点，这种思路非常的巧妙，而且实现起来也不难，跟之前那到课程清单的题一样，我们需要建立一个图g，是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。还需要一个一维数组d用来保存各个节点的入度信息，其中d[i]表示i节点的入度数。我们的目标是删除所有的叶节点，叶节点的入度为1，所以我们开始将所有入度为1的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，将该节点的入度减1，如果该节点的入度减到1了，说明此节点也也变成一个叶节点了，加入队列中，再下一轮删除。那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点啦
基本思路是“逐层删去叶子节点，直到剩下根节点为止”
有点类似于拓扑排序
最终剩下的节点个数可能为1或者2
时间复杂度：O(n)，其中n为顶点的个数。
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]
附上一开始TLE的版本
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).
http://blog.csdn.net/yaokai_assultmaster/article/details/52051181
Proof by contradiction
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:
- 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-1public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
List<Set<Integer>> adj = new ArrayList<>(n);
for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; ++i)
if (adj.get(i).size() == 1) leaves.add(i);
while (n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int i : leaves) {
int j = adj.get(i).iterator().next();
adj.get(j).remove(i);
if (adj.get(j).size() == 1) newLeaves.add(j);
}
leaves = newLeaves;
}
return leaves;
}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; }这道题虽然是树的题目，但是跟其最接近的题目是Course Schedule 课程清单和Course Schedule II 课程清单之二。由于LeetCode中的树的题目主要都是针对于二叉树的，而这道题虽说是树但其实本质是想考察图的知识，这道题刚开始在拿到的时候，我最先想到的解法是遍历的点，以每个点都当做根节点，算出高度，然后找出最小的，但是一时半会又写不出程序来，于是上网看看大家的解法，发现大家推崇的方法是一个类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点，这种思路非常的巧妙，而且实现起来也不难，跟之前那到课程清单的题一样，我们需要建立一个图g，是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。还需要一个一维数组d用来保存各个节点的入度信息，其中d[i]表示i节点的入度数。我们的目标是删除所有的叶节点，叶节点的入度为1，所以我们开始将所有入度为1的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，将该节点的入度减1，如果该节点的入度减到1了，说明此节点也也变成一个叶节点了，加入队列中，再下一轮删除。那么我们删到什么时候呢，当节点数小于等于2时候停止，此时剩下的一个或两个节点就是我们要求的最小高度树的根节点啦
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; }
基本思路是“逐层删去叶子节点，直到剩下根节点为止”
有点类似于拓扑排序
最终剩下的节点个数可能为1或者2
时间复杂度：O(n)，其中n为顶点的个数。
答案一定是最长距离的中间结点位置上。
我们要的是中间结点，沿着树的外围每次把叶子结点砍掉，那么，最后剩下的不就是中间结点了么？
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[x].append(y) #add_edge
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
http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/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
List<Integer> queue = new LinkedList<Integer>();
if (n < 2) {
queue.add(0);
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) {
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
indegree[edge[0]]++;
indegree[edge[1]]++;
}
for (int i = 0; i < count; i++){
if (indegree[i] == 1)
queue.add(i);
}
//check from the outer layer to inner layer, stop when count == 1 or 2
//which means we arrive at the center
while (count > 2) {
List<Integer> newqueue = new LinkedList<Integer>();
for (int cur: queue) {
count--;
for (int next: map.get(cur)) {
map.get(next).remove(cur);
if (--indegree[next] == 1)
newqueue.add(next);
}
}
queue = newqueue;
}
return queue;
}
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
//check for the single node situation
List<Integer> queue = new LinkedList<Integer>();
if (n < 2) {
queue.add(0);
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) {
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
indegree[edge[0]]++;
indegree[edge[1]]++;
}
for (int i = 0; i < count; i++){
if (indegree[i] == 1)
queue.add(i);
}
//check from the outer layer to inner layer, stop when count == 1 or 2
//which means we arrive at the center
while (count > 2) {
List<Integer> newqueue = new LinkedList<Integer>();
for (int cur: queue) {
count--;
for (int next: map.get(cur)) {
map.get(next).remove(cur);
if (--indegree[next] == 1)
newqueue.add(next);
}
}
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;}
// Construct adjencent graph
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) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
// Add leaves which have one leaf
for(int i = 0; i < n; i++) {
if(graph.get(i).size() == 1) leaves.add(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) {
newLeaves.add(nb);
}
}
}
leaves = newLeaves;
}
return leaves;
}
X. TODO
https://discuss.leetcode.com/topic/30956/two-o-n-solutions
List<Integer>[] e;
private void bfs(int start, int[] dist, int[] pre) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<>();
queue.add(start);
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;
queue.add(v);
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];
e[u].add(v);
e[v].add(u);
}
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) {
list.add(v);
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));
}
http://www.cnblogs.com/TonyYPZhang/p/5123058.html
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];
e[u].add(v);
e[v].add(u);
}
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++)
if (dp[i] == min) ans.add(i);
return ans;
}
https://apolloydy.wordpress.com/2015/11/26/minimum-height-trees/
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<>();
if(n <= 1) {leaves.add(0); return leaves;}
// Construct adjencent graph
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) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
// Add leaves which have one leaf
for(int i = 0; i < n; i++) {
if(graph.get(i).size() == 1) leaves.add(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) {
newLeaves.add(nb);
}
}
}
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.
http://blog.csdn.net/yaokai_assultmaster/article/details/52051181Proof%20by%20contradiction
https://nb4799.neu.edu/wordpress/?p=1996
https://discuss.leetcode.com/topic/30588/solution-share-midpoint-of-longest-path
int n;
寻找最大长度的方法有两种，一种是树的动态规划（Tree DP），一种是做两次树遍历（BFS或DFS遍历）。下面分别讨论。
- 做两次树遍历
首先任意选取树的一个结点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
|
- G = <V[1..n], E[1..n-1]>, G is connected;
- Find a path P = V[p[1]], V[p[2]], ... V[p[l]] which is the longest path in G
- 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])
a.add(j)
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]))
一种是无向图中求longest path，假如longest path长度是奇数，则结果为最中间的一个节点，否则为最中间的两个节点。思路好想到，但是并不好写。求Longest Path是一个NP-Hard问题。但对于DAG来说可以用dp来求出结果。这里un-directed graph我们也可以试一试。
超时的longest path找中点
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++) { LinkedList<Integer> path = paths.get(i); if (path.peekFirst() == edge[0]) path.addFirst(edge[1]); 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; } } paths.add(new LinkedList<>(Arrays.asList(new Integer[] {edge[0], edge[1]}))); } LinkedList<Integer> longestPath = paths.get(maxIndex); if (longestPath.size() % 2 == 0) { res.add(longestPath.get(longestPath.size() / 2 - 1)); res.add(longestPath.get(longestPath.size() / 2)); } else { res.add(longestPath.get(longestPath.size() / 2)); } return res; }https://github.com/lydxlx1/LeetCode/blob/master/src/_310.java
List<Integer>[] e;
private void bfs(int start, int[] dist, int[] pre) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<>();
queue.add(start);
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;
queue.add(v);
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];
e[u].add(v);
e[v].add(u);
}
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) {
list.add(v);
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
https://leetcode.com/problems/minimum-height-trees/discuss/76052/Two-O(n)-solutions
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.
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
- acc + 1 --- extend the previous path by edge uv;
- 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。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
.表示单独结点，*表示子树。
那么接下来我们需要考虑u的子结点，用v表示。那么v结点的acc显然等于下面两种情况中的最大值
1. acc+1 直接将u点的acc长度向uv延伸1
2. max(height[v’]+2) v’是u的子结点且v’ != v。如下图所示
那么接下来我们需要考虑u的子结点，用v表示。那么v结点的acc显然等于下面两种情况中的最大值
1. acc+1 直接将u点的acc长度向uv延伸1
2. max(height[v’]+2) v’是u的子结点且v’ != v。如下图所示
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
情况2看似需要O(k)时间（k为结点u的度），然而实际上我们只需要O(1)时间来处理情况2。方法是我们为每个结点保留其最大高度（
那么经过DFS，所有的节点的最大高度（
* 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);
}
}
}height1[]）和第二大高度（height2[]）两个量（也就是将最大高度的分支去掉后该结点的最大高度）。那么情况2，max{height[v’] + 2}就是： I. height1[u] + 1（当v不在u的最大高度所在的路径上时，也就是height1[u] != height1[v] + 1时），或 II. height2[u] + 1（当v在u的最大高度所在的路径上时，也就是height1[u] == height1[v] + 1时）。那么经过DFS，所有的节点的最大高度（
dp[]）都被计算出来之后，我们只需找到高度最小的结点返回即可。 http://www.cnblogs.com/TonyYPZhang/p/5123058.html
求最小高度的树，实际上是一个求最优解题目。求最优解，我首先想到的是动态规划(DP)思路。这个题目也确实满足 DP 的两个主要性质：overlapping substructure & optimal substructure 。思路比较直观：
- 视某个节点为树根节点，求这棵树的树高。
- 对所有节点进行上面的求解，得到 n 个树高，其中高度最小的树的树根即为原题目的解。
对于1，如何求解节点 A 为树根的树高？
假设已知 A 的所有相邻节点分别为树根的各个子树的树高，那么 A根的树高等于 已知的各个子树树高中的最大值 加一。方程式表达如下，即状态转换方程：
height(A) = max(height(A.next0), height(A.next2),... height(A.nextk)) + 1
对于2， 存在大量重复计算。可以借助表格，将已计算的树分支高度保存下来后续使用，避免重复计算。将当前节点以及其中一个相邻节点组合分支方向，求得该分支高度后存入 map<string, int> direc_height 中，其中 direc 有这两个节点组成作为 key ，height 表示高度。
若不使用表格优化，时间复杂度为 O(V*E)。使用表格，相当于进行了剪枝，会快不少。跑 LeetCode 的大集合 V = 1000, E =2000 ，测试耗时是 820ms，可惜没能过 submit 要求。
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];
e[u].add(v);
e[v].add(u);
}
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++)
if (dp[i] == min) ans.add(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; }
思路就是类似于RIP算法，通过相邻的结点更新当前结点距离。
比如说有x ,y 一条边（以x=>y举例，y=>x同样进行更新）
我们可以通过y到各个结点的距离dis[y]来更新，就是说，让x走y这条边，然后到其他结点的距离(比如i)是不是比当前不走y到i的距离小。
于是有：dis[x][i] = dis[i][x] = min(dis[i][x], dis[i][y] + 1) (无向图对称性：dis[i][y] = dis[y][i] , dis[x][i] = dis[i][x])
最后找最小的即可。
总复杂度：O(n^2)
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.htmlA 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; }Proof by contradiction
首先这道题目要考虑到的是，对于一颗给定的树，我们要寻找的最小高度树（MHT）可能有几种呢？答案是一种或两种。这个结论可以用反证法予以证明。
假设给定一棵树，我们可以找到三种不同根结点的MHT。不失普遍性的情况下，我们可以假设这三个根结点是两两相连接的，记为r1，r2和r3。假设这三者作为根结点所构成的树的高度均为h。那么r1到r3的最大距离为2（或更大，如果这三个结点不是两两相邻的话）。那么r1作为根结点所构成的MHT的高度实际上为h+2（因为r3高为h，而r1距离r3为2以上）。那么r1构成的树就不是MHT，这与我们的假设矛盾。
假设给定一棵树，我们可以找到三种不同根结点的MHT。不失普遍性的情况下，我们可以假设这三个根结点是两两相连接的，记为r1，r2和r3。假设这三者作为根结点所构成的树的高度均为h。那么r1到r3的最大距离为2（或更大，如果这三个结点不是两两相邻的话）。那么r1作为根结点所构成的MHT的高度实际上为h+2（因为r3高为h，而r1距离r3为2以上）。那么r1构成的树就不是MHT，这与我们的假设矛盾。
基于以上的结论。我们知道了实际上我们需要在给定的树中找打1个或2个结点来作为MHT的根结点。
Read full article from leetcode Minimum Height Trees - 细语呢喃