返回最低和最高键 - 二进制搜索树之间的差异

Question

这是我正在尝试的二进制搜索树的过去考试论文。我无法检查输出是否正确，因为我无法构建这些内容之一。

问题在标题中

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

您需要定义两种方法， 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;
}