O（log n）中的二叉搜索樹？

Question

給定一個具有n個節點的二叉樹，是否有可能檢查給定樹是否爲BST或O（log n）時間複雜度？

Answer 1

如果n是節點的數量，那麼不，因爲您至少需要查看一次所有值，所以您至少需要O（n）。但是如果你將n定義爲像你可以達到的子樹的總數那樣特殊的東西。 （然而，這樣做有點愚蠢，因爲這樣說如果你有100美分而不是1歐元就有更多的錢，它看起來更令人印象深刻，但也很奇怪，沒有附加價值，這只是令人困惑與正常人一起工作並不這樣做）

這裏是O（n）算法：如果它是BST，那麼左邊和右邊的樹都是BST，其中所有的值都會在一定的最小值和最大值，所以你可以創建一個去有點像這樣的遞歸方法：

public boolean isBST(subtree, minvalue, maxvalue){ 
    root=root of subtree; 
    if(root>maxvalue || root<minvalue) return false; 
    if(has left child) 
     if(!isBST(left-child-tree, minvalue, rootvalue)) return false; 
    if(has right child) 
     if(!isBST(right-child-tree, rootvalue, maxvalue)) return false; 
    return true; 
} 

，並調用此方法與isBST（樹，負無窮，正無窮大）。這是僞代碼，當然可以更好地實現。