Para un gráfico no dirigido con características de árbol, podemos elegir cualquier nodo como raíz. El gráfico de resultado es entonces un árbol enraizado. Entre todos los árboles enraizados posibles, los que tienen una altura mínima se denominan árboles de altura mínima (MHT). Dado un gráfico de este tipo, escriba una función para encontrar todos los MHT y devuelva una lista de sus etiquetas raíz.
El gráfico contiene n nodos que están etiquetados de 0 a n – 1. Se le dará el número n y una lista de bordes no dirigidos (cada borde es un par de etiquetas).
Puede suponer que no aparecerán bordes duplicados en los bordes. Dado que todos los bordes no están dirigidos, [0, 1] es lo mismo que [1, 0] y por lo tanto no aparecerán juntos en los bordes.
Ejemplo 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/
2 3
return [1]
Solución Java
public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer> result = new ArrayList<Integer>(); if(n==0){ return result; } if(n==1){ result.add(0); return result; } ArrayList<HashSet<Integer>> graph = new ArrayList<HashSet<Integer>>(); for(int i=0; i<n; i++){ graph.add(new HashSet<Integer>()); } for(int[] edge: edges){ graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } LinkedList<Integer> leaves = new LinkedList<Integer>(); for(int i=0; i<n; i++){ if(graph.get(i).size()==1){ leaves.offer(i); } } if(leaves.size()==0){ return result; } while(n>2){ n = n-leaves.size(); LinkedList<Integer> newLeaves = new LinkedList<Integer>(); for(int l: leaves){ int neighbor = graph.get(l).iterator().next(); graph.get(neighbor).remove(l); if(graph.get(neighbor).size()==1){ newLeaves.add(neighbor); } } leaves = newLeaves; } return leaves; } |
