最も低いキーと最高キーの違いを返す - バイナリ検索ツリー

Question

これは、私が試みているバイナリ検索ツリーに関する過去の試験用紙です。これらのものの1つを構築できないため、出力が正しいかどうかを確認する方法はありません。

質問はタイトルにあります

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

5/5マークを取得するために私が変更する必要があるものを誰でも提案できますか：D-私たちがしなければならない唯一のことは書くことです span 方法、ヘッダーが私たちのために与えられました。

Answer 1

2つの方法を定義する必要があります。 min(Tree) と max(Tree), 、 それから span(Tree t) と定義されている max(t) - min(t). span それ自体は再帰的であってはなりませんが、作ることができます min と max 必要に応じて再帰。

ご了承ください min と max そうではありません 持ってる 彼ら自身の方法になること。あなたがそれらを自分のユニットとして立たせたいと思っていないなら、あなたはそれをすべてに置くことができます span このような：

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