检查BT是否是BST，T<T>扩展可比较Java

Question

检查是BT是BST很简单，但我在使用可比类时正在努力算法。

首先，我有给定的BT插入方法：

public void insert(T item){
    //initialize new BT and sets left, right, parent and data to null
    BinaryTree<T> newNode = new BinaryTree<T>();
    newNode.setData(item);
    if (size==0){
        tree = newNode;
        size++;
        return;
    }
    BinaryTree<T> t = tree;
    boolean done = false;
    while (!done){
        int c = item.compareTo(t.getData());
        if (c==0){
            System.out.println("Duplicate key. Can't insert");
            return;
        }
        //need to go left
        else if (c<0){
            //place to insert found
            if (t.getLeft()==null){
                t.setLeft(newNode);
                newNode.setParent(t);
                size++;
                done = true;
            }
            else
                //otherwise go left one branch
                t = t.getLeft();
        }
        //c>0; need to go right
        else{
            //place to insert found
            if (t.getRight()==null){
                t.setRight(newNode);
                newNode.setParent(t);
                size++;
                done=true;
            }
            else
                t = t.getRight();
        }
    }
}

我将 4 2 5 1 3 插入 BT，将 1 2 3 4 插入 BT 树看起来像：

四 /\ 2   5 /\ 1   3  1 \  2 \  3 \  4

并且结果仍然返回 true。

对于 BST 的验证方法：

public static<T extends Comparable<T>> boolean isBinarySearchTree(BinaryTree<T> t){
    if(t ==null){
        return true;
    }
    if(t.getLeft()!=null && t.getLeft().getData().compareTo(t.getData())>0){
        return false;
    }
    if(t.getRight() !=null && t.getRight().getData().compareTo(t.getData())<0){
        return false;
    }
    return isBinarySearchTree(t.getLeft()) && isBinarySearchTree(t.getRight());
}

我想使用 T 扩展可比较<>，并将二进制树 t 输入到方法中。
但是我很困惑为什么该方法仍然确定第二个BT也是BST。

Answer 1

如何添加一个额外的高度方法：

int height(BinaryTree bt) {
    if (bt == null) {
       return 0;
    }
    return 1 + Math.max(height(bt.getLeft()), height());
}

然后在isBinarySearchTree检查中添加一个额外的if语句：

if (height(t.getRight()) != height(t.getLeft())) {
    return false;
}

这增加了O(log n(的复杂性，因为它可能在每个级别上都贯穿树的高度。