Devuelva la diferencia entre la clave más baja y la más alta - Árbol de búsqueda binario

Question

Este es un examen anterior sobre árboles de búsqueda binarios que estoy intentando. No tengo forma de verificar si la salida es correcta, ya que no soy capaz de construir una de estas cosas.

la pregunta está en el título

class Tree{
    Tree left;
    Tree right;
    int key;

   public static int span(Tree tree)
   {
        if ( tree == null ){
             return null;
        }

        if( tree.left != null)
             int min = span(tree.left);
         }

        if( tree.right != null){
             int max = span(tree.right);
         }
         return max - min;
    }
}

¿Alguien podría sugerir lo que necesito cambiar para obtener 5/5 puntos: D - Lo único que tenemos que hacer es escribir el span Método, el encabezado fue dado para nosotros.

Answer 1

Necesitas definir dos métodos, min(Tree) y max(Tree), después span(Tree t) Se define como max(t) - min(t). span en sí mismo no debería ser recursivo, pero puedes hacer min y max recursivo si quieres.

Tenga en cuenta que min y max no tener ser sus propios métodos. Si no te importa hacer que se paren como sus propias unidades, puedes ponerlo todo en span como esto:

int span(Tree t) {
   Tree tMin = t;
   while (tMin.left != null) {
      tMin = tMin.left;
   }

   Tree tMax = t;
   while (tMax.right != null) {
      tMax = tMax.right;
   }

   return tMax.key - tMin.key;
}