=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2024/2025
29 de noviembre de 2024 (arboles, aplazado 8 de noviembre))
Ejercicio
Borrador
=================================================================


Solucion apartado a
===================

Coste temporal en el peor caso: O(n)
Coste espacial en el peor caso sin contar el arbol: O(log n)

int Diccionario::minimaProfundidadEquipo(int e) const {
   int resultado = -1;
   minimaProfundidadEquipo(e, raiz, 0, resultado);
   return resultado;
}

void Diccionario::minimaProfundidadEquipo(int e, Nodo * n, int profundidad, int & resultado) const {

   if (n == nullptr)
      return;

   if (n->equipo == e) {
      resultado = profundidad;
      return;
   }

   if (resultado == -1 || profundidad + 1 < resultado)
      minimaProfundidadEquipo(e, n->izquierdo, profundidad + 1, resultado);

   if (resultado == -1 || profundidad + 1 < resultado)
      minimaProfundidadEquipo(e, n->derecho, profundidad + 1, resultado);
      
}


Solucion apartado b
===================

Coste temporal en el peor caso: O(n)
Coste espacial en el peor caso sin contar el arbol: O(n)

int Diccionario::minimaProfundidadEquipo(int e) const {

   if (raiz == nullptr)
      return -1;

   if (raiz->equipo == e)
      return 0;

   queue<Nodo *> cola;
   cola.push(raiz);
   int profundidad = 0;

   while(! cola.empty()) {
      int tallaNivel = cola.size();
      for (int i = 0; i < tallaNivel; i++) {
	 Nodo * n = cola.front();
	 cola.pop();
	 if (n->izquierdo != nullptr) {
	    if (n->izquierdo->equipo == e)
	       return profundidad + 1;
	    cola.push(n->izquierdo);
	 }
	 if (n->derecho != nullptr) {
	    if (n->derecho->equipo == e)
	       return profundidad + 1;
	    cola.push(n->derecho);
	 }
      }
      profundidad++;
   }
   return -1;

}