题目
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 from0
ton - 1
. You will be given the number n and a list of undirectededges
(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 inedges
.
Example 1 :
1
2
3
4
5
6
7
8
9Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]Example 2 :
1
2
3
4
5
6
7
8
9
10
11Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]Note:
- 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.”
- The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
解题思路
解法1 - 暴力破解(超时
,Failed
)
- 步骤
- 以每个节点都为根,对每个节点使用BFS遍历得到以该节点为根时树的高度
- 比较各个节点时树的高度,得到
Minimum Height Trees
的根节点
- 代码
1
2
3
4
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> v;
int edgesArray[n][n];
int height[n];
for(int i = 0; i < n; ++i) {
height[i] = getHeight(n, i, edges);
}
// 寻找最小高度树的根节点
int min = n;
for(int i = 0; i < n; ++i) {
if(height[i] < min) {
min = height[i];
v.clear();
v.push_back(i);
}
else if(height[i] == min) {
v.push_back(i);
}
}
return v;
}
// bfs遍历
int getHeight(int n, int root, vector<pair<int, int> >& edges) {
int h = 0;
int visited[n] = {0};
visited[root] = 1;
queue<int> q;
q.push(root);
int depth[n] = {0};
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(auto iter = edges.begin(); iter != edges.end(); iter++) {
if((*iter).first == tmp || (*iter).second == tmp) {
int newNode = (*iter).first + (*iter).second - tmp;
if(!visited[newNode]) {
depth[newNode] = depth[tmp] + 1;
q.push(newNode);
visited[newNode] = 1;
}
}
}
}
int max = 0;
for(int i = 0; i < n; ++i) {
if(depth[i] > max)
max = depth[i];
}
return max;
}
}; - 复杂度 — $O(V^2E)$ (
V
表示节点数量,E
表示边的数量) - 结果果然超时了
- 改进与优化
- 可以利用map数据结构,来存储每个节点对应其连接的节点所组成的一个映射
map<int, vector<int> >
,或者一个二维数组 - 复杂度 — $O(VE)$ (
V
表示节点数量,E
表示边的数量) - 优化的代码
1
2
3
4
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> v;
map<int, vector<int> > myMap;
int height[n];
for(auto iter = edges.begin(); iter != edges.end(); iter++) {
myMap[(*iter).first].push_back((*iter).second);
myMap[(*iter).second].push_back((*iter).first);
}
for(int i = 0; i < n; ++i) {
height[i] = getHeight(n, i, myMap);
}
// 寻找最小高度树的根节点
int min = n;
for(int i = 0; i < n; ++i) {
if(height[i] < min) {
min = height[i];
v.clear();
v.push_back(i);
}
else if(height[i] == min) {
v.push_back(i);
}
}
return v;
}
// bfs遍历
int getHeight(int n, int root, map<int, vector<int> > myMap) {
int h = 0;
int visited[n] = {0};
visited[root] = 1;
queue<int> q;
q.push(root);
int depth[n] = {0};
while(!q.empty()) {
int tmp = q.front();
q.pop();
for(auto iter = myMap[tmp].begin(); iter != myMap[tmp].end(); iter++) {
if(!visited[(*iter)]) {
depth[(*iter)] = depth[tmp] + 1;
q.push((*iter));
visited[(*iter)] = 1;
}
}
}
int max = 0;
for(int i = 0; i < n; ++i) {
if(depth[i] > max)
max = depth[i];
}
return max;
}
}; - 但是依旧超时
- 可以利用map数据结构,来存储每个节点对应其连接的节点所组成的一个映射
思考提示:How many MHTs can a graph have at most?
- 每个树最多有两个MHTs。假如有三个或多个可以作为MHTs的根节点,根据树的定义,每两个节点都可以找到一条路径连接起来,树是一个强连通的图,不存在简单环,则至少一个一个或多个比其余节点高,则大于三个MHTs不成立。
解法2 — 类剥洋葱求解(AC
)
- 本方法学习自其他优秀解法
- 步骤
- 建立一个映射表,记录每一个点与其直接相连的点
- 将树的叶节点(度为1的节点)加入一个队列中
- 假如当前队列中存储的节点数小于等于2,则退出循环。否则遍历队列中的每个节点。对每个节点,将其弹出队列,同时将与其相连节点的集合中将该节点删去,如果删完该节点后此节点也变成一个叶节点(度数为1),那么将这个节点加入队列中。
- 时间复杂度 — $O(n)$
- 实现代码
1
2
3
4
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
36class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if(n == 1) return {0};
vector<int> ans;
vector<set<int> > myVec(n);
for(auto edge : edges) {
myVec[edge.first].insert(edge.second);
myVec[edge.second].insert(edge.first);
}
queue<int> q;
for(int i = 0; i < n; ++i)
if(myVec[i].size() == 1)
q.push(i);
while(n > 2) {
int size = q.size();
n -= size;
for(int i = 0; i < size; ++i) {
int tmp = q.front();
q.pop();
for (auto it : myVec[tmp]) {
myVec[it].erase(tmp);
if (myVec[it].size() == 1) q.push(it);
}
}
}
while(!q.empty()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};