¿Árbol binario con elementos repetidos?

Question

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).

Actualizar:

¿Se podía hacer con un iterador?

Answer 1

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.