题目描述
题目链接:310. Minimum Height Trees
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.
Given a tree of n nodes labelled from
0
ton - 1
, and an array ofn - 1
edges whereedges[i] = [ai, bi]
indicates that there is an undirected edge between the two nodesai
andbi
in the tree, you can choose any node of the tree as the root. When you select a nodex
as the root, the result tree has heighth
. Among all possible rooted trees, those with minimum height (i.e.min(h)
) are called minimum height trees (MHTs).Return a list of all MHTs' root labels. You can return the answer in any order.
The
height
of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
例子
例子见上方原题链接。
Constraints
1 <= n <= 2 * 10^4
edges.length == n - 1
0 <= ai, bi < n
ai != bi
- All the pairs (
ai
,bi
) are distinct.- The given input is guaranteed to be a tree and there will be no repeated edges.
解题思路
这道题给定条件是保证输入是一个合法的树,因此暴力解法是以每个节点为根节点使用广度优先搜索往下遍历,求出高度。并根据高度筛选出结果。每次遍历时间复杂度是 O(n)
因此最后复杂度是 O(n)
。根据给定的数据规模判断不可行。
我们可以转换思路,虽然每个节点都有可能是根节点,但是根据例子来看,当节点数大于3时,最小高度树的根节点的边数都不为1,这很好理解,为了让高度最小,从根节点开始每一层都应该有尽量多的节点。因此我们可以从叶节点(只有一条边)出发往上遍历,每次遍历一个节点叶节点时将其链接的边去除,如果去除后其邻居的边数只有1,表示找到了一个新的叶节点。每一次循环相当于从外部向内部去除了一层最外层叶节点,当最后遍历结束后,最后一次遍历的叶节点都可以作为根节点。
代码如下:
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
class Solution {
public:
std::vector<int> findMinHeightTrees(int n,
std::vector<std::vector<int>>& edges) {
std::vector<int> roots;
std::vector<std::unordered_set<int>> graph(n);
for (auto edge : edges) {
graph[edge[0]].insert(edge[1]);
graph[edge[1]].insert(edge[0]);
}
std::queue<int> leaves;
std::unordered_set<int> visited;
for (int i = 0; i < n; ++i) {
if (graph[i].size() == 1) {
leaves.push(i);
} else if (graph[i].empty()) {
return {i};
}
}
while (!leaves.empty()) {
std::queue<int> next_leaves;
while (!leaves.empty()) {
int node = leaves.front();
leaves.pop();
roots.push_back(node);
for (int nei : graph[node]) {
// remove this edge
graph[nei].erase(node);
// if it becomes a new node, add it to the queue
if (graph[nei].size() == 1) {
next_leaves.push(nei);
}
}
graph[node].clear();
}
if (!next_leaves.empty()) {
roots.clear();
std::swap(next_leaves, leaves);
}
}
return roots;
}
};
- 时间复杂度:
O(|E|+|N|)
- 空间复杂度:
O(|E|+|N|)
GitHub 代码同步地址: 310.MinimumHeightTrees.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions