Restituisci la differenza tra la chiave più bassa e più alta - Binaria di ricerca

Question

Questo è un documento di esame passato sugli alberi di ricerca binari che sto tentando. Non ho modo di verificare se l'output è corretto in quanto non sono in grado di costruire una di queste cose.

La domanda è nel titolo

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;
    }
}

Qualcuno potrebbe suggerire cosa devo cambiare per ottenere 5/5 marchi: D - L'unica cosa che dobbiamo fare è scrivere il span Metodo, l'intestazione è stata data per noi.

Answer 1

Devi definire due metodi, min(Tree) e max(Tree), poi span(Tree t) è definito come max(t) - min(t). span se stesso non dovrebbe essere ricorsivo, ma puoi fare min e max ricorsivo se vuoi.

Notare che min e max no avere essere i loro metodi. Se non ti interessa farli stare in piedi come le loro unità, puoi inserire tutto span come questo:

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;
}