Gibt den Unterschied zwischen dem niedrigsten und höchsten Schlüssel zurück - binärer Suchbaum

Question

Dies ist eine frühere Prüfungspapier über binäre Suchbäume, die ich versuche. Ich habe keine Möglichkeit zu überprüfen, ob die Ausgabe korrekt ist, da ich nicht in der Lage bin, eines dieser Dinge zu bauen.

Die Frage ist im Titel

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

Könnte jemand vorschlagen, was ich ändern muss, um 5/5 Punkte zu erhalten: D - Das einzige, was wir tun müssen, ist, die zu schreiben span Methode, der Header wurde für uns gegeben.

Answer 1

Sie müssen zwei Methoden definieren, min(Tree) und max(Tree), dann span(Tree t) ist definiert als max(t) - min(t). span selbst sollte nicht rekursiv sein, aber Sie können machen min und max rekursiv, wenn Sie wollen.

Beachten Sie, dass min und max nicht haben ihre eigenen Methoden sein. Wenn Sie es nicht interessieren, sie als ihre eigenen Einheiten zu halten, können Sie alles einsetzen span so was:

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