310. Minimum Height Trees
Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом.
Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).
Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.
Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.
Пример:
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
C# решение
сопоставлено/оригиналpublic class Solution {
public IList<int> FindMinHeightTrees(int n, int[][] edges) {
if (n == 1) return new List<int> { 0 };
var adj = new List<HashSet<int>>();
for (int i = 0; i < n; i++) adj.Add(new HashSet<int>());
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
var leaves = new List<int>();
for (int i = 0; i < n; i++) {
if (adj[i].Count == 1) leaves.Add(i);
}
int remainingNodes = n;
while (remainingNodes > 2) {
remainingNodes -= leaves.Count;
var newLeaves = new List<int>();
foreach (var leaf in leaves) {
var neighbor = adj[leaf].First();
adj[neighbor].Remove(leaf);
if (adj[neighbor].Count == 1) newLeaves.Add(neighbor);
}
leaves = newLeaves;
}
return leaves;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int> FindMinHeightTrees(int n, int[][] edges) {
if (n == 1) return new List<int> { 0 };
var adj = new List<HashSet<int>>();
for (int i = 0; i < n; i++) adj.push_back(new HashSet<int>());
foreach (var edge in edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
var leaves = new List<int>();
for (int i = 0; i < n; i++) {
if (adj[i].size() == 1) leaves.push_back(i);
}
int remainingNodes = n;
while (remainingNodes > 2) {
remainingNodes -= leaves.size();
var newLeaves = new List<int>();
foreach (var leaf in leaves) {
var neighbor = adj[leaf].First();
adj[neighbor].Remove(leaf);
if (adj[neighbor].size() == 1) newLeaves.push_back(neighbor);
}
leaves = newLeaves;
}
return leaves;
}
}Java решение
сопоставлено/оригиналpublic class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
List<Set<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new HashSet<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (adj.get(i).size() == 1) leaves.add(i);
}
int remainingNodes = n;
while (remainingNodes > 2) {
remainingNodes -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int leaf : leaves) {
int neighbor = adj.get(leaf).iterator().next();
adj.get(neighbor).remove(leaf);
if (adj.get(neighbor).size() == 1) newLeaves.add(neighbor);
}
leaves = newLeaves;
}
return leaves;
}
}JavaScript решение
сопоставлено/оригиналvar findMinHeightTrees = function(n, edges) {
if (n === 1) return [0];
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
let leaves = [];
for (let i = 0; i < n; i++) {
if (adj[i].length === 1) leaves.push(i);
}
let remainingNodes = n;
while (remainingNodes > 2) {
remainingNodes -= leaves.length;
const newLeaves = [];
for (const leaf of leaves) {
const neighbor = adj[leaf][0];
adj[neighbor] = adj[neighbor].filter(node => node !== leaf);
if (adj[neighbor].length === 1) newLeaves.push(neighbor);
}
leaves = newLeaves;
}
return leaves;
};Python решение
сопоставлено/оригиналclass Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
from collections import defaultdict, deque
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
leaves = deque()
for i in range(n):
if len(adj[i]) == 1:
leaves.append(i)
remaining_nodes = n
while remaining_nodes > 2:
leaves_size = len(leaves)
remaining_nodes -= leaves_size
for _ in range(leaves_size):
leaf = leaves.popleft()
neighbor = adj[leaf].pop()
adj[neighbor].remove(leaf)
if len(adj[neighbor]) == 1:
leaves.append(neighbor)
return list(leaves)Go решение
сопоставлено/оригиналpackage main
func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{0}
}
adj := make([]map[int]bool, n)
for i := 0; i < n; i++ {
adj[i] = make(map[int]bool)
}
for _, edge := range edges {
adj[edge[0]][edge[1]] = true
adj[edge[1]][edge[0]] = true
}
leaves := []int{}
for i := 0; i < n; i++ {
if len(adj[i]) == 1 {
leaves = append(leaves, i)
}
}
remainingNodes := n
for remainingNodes > 2 {
remainingNodes -= len(leaves)
newLeaves := []int{}
for _, leaf := range leaves {
for neighbor := range adj[leaf] {
delete(adj[neighbor], leaf)
if len(adj[neighbor]) == 1 {
newLeaves = append(newLeaves, neighbor)
}
}
delete(adj, leaf)
}
leaves = newLeaves
}
return leaves
}Algorithm
Создание списка смежности
Создайте список смежности, представляющий граф.
Удаление листьев
Начните с удаления всех листьев. Лист — это узел с одной гранью. В каждой итерации удаляйте текущие листья и обновляйте список смежности. Новые листья будут вершинами, которые стали листьями после удаления предыдущих листьев.
Повторение процесса
Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT).
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.