方法一:树形DP
要求树的最小高度,其实还是枚举,分别求出每个点到其他节点的最远距离(就是高度),因为要求出每个点,所以需要记录往下走的和往上走的两类节点。所以多了一个up
数组和 d2
数组,做了两次dfs
,一次自下而上递归求出 d1
和 d2
石子,一次自上而下递归求出 up
数组。
class Solution {
public:
vector<vector<int>> g;
vector<int> d1, d2, p1, p2, up; // d1和d2记录往下走的最大长度和次大长度 p1, p2记录最大值和次大值是从哪个点下去的 up记录往上走的最大长度
void dfs1(int u, int fa) {
for(int j : g[u]) {
if (j == fa) continue;
dfs1(j, u); // 自下而上递归
int d = d1[j] + 1;
if (d >= d1[u]) {
d2[u] = d1[u], d1[u] = d;
p2[u] = p1[u], p1[u] = j;
} else if (d > d2[u]){
d2[u] = d, p2[u] = j;
}
}
}
void dfs2(int u, int fa) {
for (int j : g[u]) {
if (j == fa) continue;
if (p1[u] == j) up[j] = max(up[u], d2[u]) + 1;
else up[j] = max(up[u], d1[u]) + 1;
dfs2(j, u); // 自上而下递归
}
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
g.resize(n);
d1 = d2 = p1 = p2 = up = vector<int>(n);
// 找一下每个点到其他所有点的最大距离,找到最大距离最小的点作为根节点
for (auto& edge : edges) {
int a = edge[0], b = edge[1];
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(0, -1); // 不能枚举根节点,时间复杂度O(n^2),用树形dp求出所有点往上走和往下走的最大值
dfs2(0, -1); // 求up数组
int mn = n + 1;
for (int i = 0; i < n; i++) mn = min(mn, max(d1[i], up[i]));
vector<int> res;
for (int i = 0; i < n; i++)
if (max(d1[i], up[i]) == mn)
res.push_back(i);
return res;
}
};
相似例题:1072. 树的最长路径,1207. 大臣的旅费
方法二:拓扑排序
如果这棵树只有一个节点,那么这个节点就是最小高度树的根节点,直接返回这个节点即可。
如果这棵树有多个节点,那么一定存在叶子节点。叶子节点是只有一个相邻节点的节点。我们可以利用拓扑排序,从外向内剥离叶子节点,当我们到达最后一层的时候,剩下的节点就可作为最小高度树的根节点。
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
vector<vector<int>> g(n);
vector<int> d(n);
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].push_back(b);
g[b].push_back(a);
++d[a];
++d[b];
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (d[i] == 1) q.push(i);
}
vector<int> res;
while (q.size()) {
res.clear();
for (int i = q.size(); i > 0; i--) {
// 将当前度数为1的点全部出队
int t = q.front();
q.pop();
res.push_back(t);
for (int x : g[t]) {
if (--d[x] == 1) q.push(x);
}
}
}
return res;
}
};
相似例题:LC 2603. 收集树中金币
首先,我们可以不断地移除给定无根树中没有金币的「叶节点」。当某个「叶节点」被移除后,它唯一相邻的那条边也需要被移除,这样可能会有新的节点变为「叶节点」。我们不断迭代地重复这个过程,直到所有的「叶节点」上都有金币为止。
当所有的「叶节点」上都有金币时,我们应该如何解决给定的问题呢?我们可以先思考,如果操作变为「收集距离当前节点距离为 0
以内的所有金币」该如何解决。当距离为 0
时,我们必须要走到对应的节点上才能收集金币,而每个「叶节点」上都有金币,因此我们必须遍历到所有的「叶节点」,这也意味着我们遍历了整颗树。从任一节点出发,遍历整颗树并返回原节点,会经过树上的每条边一次,而树的边数等于点数减一,因此答案为2(n′−1)
,其中 n′
是经过上文移除后,无根树中节点的数量。
如果操作变为「收集距离当前节点距离为 1
以内的所有金币」呢?我们可以进一步思考得到:当我们即将遍历到「叶节点」时,可以直接返回,因为此时我们与「叶节点」的距离为 1
,可以直接收集到金币,不需要走到「叶节点」。因此,我们遍历的范围,就是将树中所有叶节点以及它们唯一相邻的那条边移除后的新树。在新树中的金币可以通过遍历获得到,而不在新树中的金币会在遍历到与其距离为 1
的某个节点时获取到。
因此,当操作变为「收集距离当前节点距离为 2
以内的所有金币」时,我们的方法仍然是类似的,我们只需要将新树中所有的「叶节点」以及它们唯一相邻的那条边移除,得到的新新树就是需要遍历的范围。
class Solution {
public:
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
vector<vector<int>> g(n);
vector<int> degree(n);
for (const auto& edge: edges) {
int x = edge[0], y = edge[1];
g[x].push_back(y);
g[y].push_back(x);
++degree[x];
++degree[y];
}
// 统计删除三次后的节点数量
int rest = n;
{
/* 删除树中所有无金币的叶子节点,直到树中所有的叶子节点都是含有金币的 */
queue<int> q;
for (int i = 0; i < n; ++i) {
if (degree[i] == 1 && !coins[i]) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
--degree[u];
q.pop();
--rest;
for (int v: g[u]) {
--degree[v];
if (degree[v] == 1 && !coins[v]) {
q.push(v);
}
}
}
}
{
/* 删除树中所有的叶子节点, 因为可以走两步,所以要删除两次 */
for (int _ = 0; _ < 2; ++_) {
queue<int> q;
for (int i = 0; i < n; ++i) {
if (degree[i] == 1) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
--degree[u];
q.pop();
--rest;
for (int v: g[u]) {
--degree[v];
}
}
}
}
return rest == 0 ? 0 : (rest - 1) * 2;
}
};