確定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/