题目
题目链接🔗
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n n n 个节点的树,标记为 0 0 0 到 n − 1 n - 1 n−1 。给定数字 n 和一个有 n - 1 条无向边的 e d g e s edges edges 列表(每一个边都是一对标签),其中 e d g e s [ i ] = [ a i , b i ] edges[i] = [a_i, b_i] edges[i]=[ai,bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h h h 。在所有可能的树中,具有最小高度的树(即, m i n ( h ) min(h) min(h))被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例 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 ∗ 1 0 4 1 \leq n \leq 2 * 10^4 1≤n≤2∗104
- e d g e s . l e n g t h = = n − 1 edges.length == n - 1 edges.length==n−1
- 0 ≤ a i , b i < n 0 \leq a_i , b_i < n 0≤ai,bi<n
- a i ≠ b i a_i \neq b_i ai=bi
- 所有 ( a i , b i ) (a_i, b_i) (ai,bi) 互不相同
- 给定的输入 保证 是一棵树,并且 不会有重复的边
思路
可以使用拓扑排序的思想来解决这个问题。首先我们统计每个节点的度数(即相邻节点的数量),然后从度数为1的叶节点开始向内部进行层次遍历。层次遍历的过程类似从树的外围向内部移动。我们从队列中取出这些节点,并将它们从图中删除(减少与之相连的节点数)。接着,继续查找新的度数为1的叶节点,知道队列为空。在这个过程中。始终标记每一层记录剩余的节点,这些节点可能是最小高度树的根节点。
代码
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges)
{
if (n == 1)
{
return {0};
}
vector<int> degree(n);
vector<vector<int>> mp(n);
vector<int> ans;// 结果
for (int i = 0; i < edges.size(); i++)
{
int u = edges[i][0];
int v = edges[i][1];
degree[u]++;
degree[v]++;
mp[u].emplace_back(v);
mp[v].emplace_back(u);
}
queue<int> q;
for (int i = 0; i < n; i++)
{
if (degree[i] == 1)
{
q.push(i);
}
}
while (!q.empty())
{
ans.clear();
int sz = q.size();
for (int i = 0; i < sz; i++)
{
int node = q.front();
q.pop();
ans.emplace_back(node);
degree[node]--;
for(int j : mp[node])
{
degree[j]--;
if(degree[j] == 1)
{
q.push(j);
}
}
}
}
return ans;
}
};
复杂度分析
时间复杂度
需要遍历所有的边来统计节点的度数,这一步需要 O(n) 的时间复杂度。接着,在层次遍历的过程中,每个节点都只会被访问一次,因此层次遍历的时间复杂度也是 O(n)。因此,总的时间复杂度为 O(n)。
空间复杂度
需要使用额外的空间来存储节点的度数、邻接表以及队列。因此,总的空间复杂度为 O(n)。
结果
总结
通过拓扑排序的思想,我们可以在线性时间内找到所有可能的最小高度树的根节点。这个算法非常高效,适用于大多数情况下的树结构。