Leetcode-310-最小高度树
|字数总计:1.7k|阅读时长:6分钟|阅读量:|
题目
原文
原题链接
树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
样例输入： n = 4, edges = [[1,0],[1,2],[1,3]]
样例输出： [1]
示例 1：
输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
示例 2：
输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]
提示：
- 1 <= n <= 2 * 104
- edges.length == n - 1
- 0 <= ai, bi < n
- ai != bi
- 所有 (ai, bi) 互不相同
- 给定的输入 保证 是一棵树，并且 不会有重复的边
代码模板
1
2
3
4
5
6
| class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
}
};
|
解题
树的最长路径即树的直径.
树的直径 - OI Wiki
显然，一棵树可以有多条直径，他们的长度相等。
可以用求两次最长路径点或者树形 DP 的方法在O(n) 时间复杂度求出树的直径。
-
方法一: 通过两次寻求最长路径
- 从任意一点P出发, 找到最远点x, 再从x出发, 找到最远点y, 则x, y的距离就是树的直径. 证明参考OI Wiki
-
方法二: 树形DP
- 从某个点出发, 求其最远距离与次远距离, 两者之和
前置准备
定义三个成员变量, 并初始化如下
1
2
3
4
5
6
7
8
| this->n = n;
this->adj = vector<vector<int>>(n);
this->parent = vector<int>(n, -1);
for (auto & edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
|
n: 结点数目
adj: 通过邻接表存储邻接关系, adj[i]表示结点i的邻接点列表
parent[i]: 表示在寻找出的路径中, 结点i的上一结点
寻求两次最长路径
BFS
最基础的BFS遍历代码如下,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int findLonestNode(int u) {
queue<int> q;
vector<bool> visit(n);
q.push(u);
visit[u] = true;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int& v: adj[cur]) {
if(visit[v]) continue;
visit[v] = true;
q.push(v);
}
}
}
|
考虑到最后一次访问的结点一定是最远的结点, 故TODO处使用一个变量不断记录, 最终循环结束时候, 该变量记录的结点便是距离u最远的结点.
遍历邻居时, 若遍历到未访问的结点, 则需要记录到parent数组中, 以得到最终的确定的路径.
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
| int findLonestNode(int u) {
queue<int> q;
vector<bool> visit(n);
q.push(u);
visit[u] = true;
int node;
while(!q.empty()) {
int cur = q.front();
q.pop();
node = cur;
for(int& v: adj[cur]) {
if(visit[v]) continue;
visit[v] = true;
parent[v] = cur;
q.push(v);
}
}
return node;
}
|
DFS
<未完待续>
求树的直径
-
任取树上一点, 求最长路径的点x
-
取点x为起点, 求最长路径的点y
-
同时记录从x到y的走过的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int x = findLongestNode(0);
int y = findLongestNode(x);
vector<int> path;
parent[x] = -1;
while (y != -1) {
path.push_back(y);
y = parent[y];
}
|
现在path数组中记录的顶点就是最长路径中从y出发到x的所有点(path[0] == y, path[path.size()-1] == x)
求使树高度最小的根结点
设m = path.size()
先说结论,
-
若m为奇数, 则使树高度最小的点为最长路径的中点. 即点path[m/2]
-
若m为偶数, 则使树高度最小的点为最中间的两个顶点, 即点path[m/2]与path[m/2-1]
官方题解证明
算法导论 习题解答9-1
1
2
3
4
5
6
7
8
9
|
int m = path.size();
if (m % 2 == 0) {
return {path[m / 2 - 1], path[m / 2]};
} else {
return {path[m / 2]};
}
|
完整代码
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
59
60
61
62
63
64
65
| class Solution {
public:
int n;
vector<vector<int>> adj;
vector<int> parent;
int findLongestNode(int u) {
queue<int> qu;
vector<bool> visit(n);
qu.push(u);
visit[u] = true;
int node = -1;
while (!qu.empty()) {
int curr = qu.front();
qu.pop();
node = curr;
for(int& v:adj[curr]) {
if (visit[v]) continue;
visit[v] = true;
parent[v] = curr;
qu.push(v);
}
}
return node;
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
this->n = n;
this->adj = vector<vector<int>>(n);
this->parent = vector<int>(n, -1);
for (auto & edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int x = findLongestNode(0);
int y = findLongestNode(x);
vector<int> path;
parent[x] = -1;
while (y != -1) {
path.push_back(y);
y = parent[y];
}
int m = path.size();
if (m % 2 == 0) {
return {path[m / 2 - 1], path[m / 2]};
} else {
return {path[m / 2]};
}
}
};
|
