¿Árbol binario con elementos repetidos?
En un árbol binario con elementos repetidos, ¿cómo harías/qué método usarías para saber qué elementos estan repetidos? (Es decir, que te devuelva la cantidad de elementos repetidos y cuales son).
¿Se podía hacer con un iterador?
1 respuesta
- ?Lv 7hace 8 meses
Se podría hacer de manera iterativa o recursiva. Yo usaría un hash para marcar los nodos ya vistos y otro hash diferente para marcar los repetidos.
void markRepeated(TreeNode node, Set<Integer> seen, Set<Integer> repeated) {
if (node == null) {
return;
}
if (seen.contains(node.val)) {
repeated.add(node.val);
} else {
seen.add(node.val);
}
markRepeated(node.left, seen, repeated);
markRepeated(node.right, seen, repeated);
}
Y mandaría llamar el método así.
Set<Integer> repeated = new HashSet<>();
markRepeated(root, new HashSet<>(), repeated);
Al final, repeated contendría todos los elementos repetidos y cuáles son.