## [Leetcode]310. Minimum Height Trees(C++)

### 题目描述

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` to `n - 1`, and an array of `n - 1` edges where `edges[i] = [ai, bi]` indicates that there is an undirected edge between the two nodes `ai` and `bi` in the tree, you can choose any node of the tree as the root. When you select a node `x` as the root, the result tree has height `h`. 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.

### 解题思路

``````#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

Built with Hugo
Theme Stack designed by Jimmy