java - 确定BST的高效算法

Question

我想知道这种检查 BST 的方法是否正确且有效。

我的代码是判断树是否为二叉搜索树。请随意更正，但它必须是下面的方法，并且被要求检查一次树中的每个节点。

需要使用此方法调用:public static boolean isBST(BinaryTree<String> tree)

下面是我的算法和代码:

public static boolean isBST(BinaryTree<String> tree)
{
    return isBST(tree.root);
}

private static boolean isBST(BinaryNode<String> root) {

    if(root==null)
        return true;
    else{
        if(root.getLeftChild().getData().compareTo(root.getData())<0&&root.getRightChild().getData().compareTo(root.getData())>0)
            return true;
        else
            return false;
    }
}

我采用这种方法是因为使用泛型和静态方法。

Answer 1

您发布的代码只是检查根节点的直接子节点是否遵循 BST 属性。但是，您需要对整个左右子树执行此操作。一种实现方法如下:

public static boolean isBST(BinaryTree<String> tree) {
    return isBSTChecker(tree.root, MIN, MAX);
}

public static boolean isBSTChecker(BinaryNode<String> node, T min, T max) {
    if(node == null) return true;
    else if(node.getData().compareTo(min) < 0 || node.getData().compareTo(min) > 0) return false;
    else return isBSTChecker(node.getLeftChild(), min, node.getData()) && isBSTChecker(node.getRightChild(), node.getData(), max);
}

在此方法中，您需要为泛型定义 MIN 和 MAX 值。一种方法是遍历整棵树并找到最小值和最大值。该方法的时间复杂度为 O(n)，并且使用常量额外空间。

另一种实现检查器的方法如下:

ArrayList<BinaryNode> list = new ArrayList<>();

public static boolean isBST(BinaryTree<String> tree) {
    inOrder(tree.root);
    return isBSTChecker(list);
}

public static boolean isBSTChecker(ArrayList<BinaryNode> inorder) {
    boolean isBST = true;
    BinaryNode prev = inorder.get(0);
    for(int i=1; i<inorder.size(); i++) {
        BinaryNode curr = inorder.get(i);
        if(curr.getData().compareTo(prev.getData()) < 0) {
             isBST = false;
             break;
        }
        prev = curr;
    }
    return isBST;
}

public static void inOrder(BinaryNode<String> node) {
    if(node == null) return;
    inOrder(node.getLeftChild());
    list.add(node);
    inOrder(node.getRightChild());
}

在该方法中，我们首先对树进行中序遍历，然后检查遍历结果是否按升序排序。该方法的时间和空间复杂度均为 O(n)。您可以通过在中序遍历期间跟踪先前访问过的节点并检查当前节点的数据是否大于先前确定的节点来消除线性空间复杂度。

来源:http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/