Retorne a diferença entre a chave mais baixa e a mais alta - a árvore de pesquisa binária

Question

Este é um artigo de exame anterior sobre árvores de pesquisa binária que estou tentando. Não tenho como verificar se a saída está correta, pois não sou capaz de construir uma dessas coisas.

A questão está no 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;
    }
}

Alguém poderia sugerir o que eu preciso mudar para obter 5/5 notas: D - A única coisa que temos que fazer é escrever o span Método, o cabeçalho foi dado para nós.

Answer 1

Você precisa definir dois métodos, min(Tree) e max(Tree), então span(Tree t) é definido como max(t) - min(t). span por si só não deve ser recursivo, mas você pode fazer min e max recursivo se você quiser.

Observe que min e max não tenho ser seus próprios métodos. Se você não se importa em fazê -los permanecer como suas próprias unidades, você pode colocar tudo em span assim:

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