其實那是每個人在面試中犯的錯誤。

必須根據（minLimitof node，node.value）檢查Leftchild

必須根據（node.value，nodeMaxLimit）檢查Rightchild

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 

{

     if(node == null)

         return true;

     if(node.element > MIN 

         && node.element < MAX

         && IsValidBST(node.left,MIN,node.element)

         && IsValidBST(node.right,node.element,MAX))

         return true;

     else 

         return false;

}

另一個解決方案（如果空間不是約束）：對樹進行有序遍歷，并將節點值存儲在數組中。如果數組按排序順序排列，則其有效的BST否則無效。

“驗證”二進制搜索樹意味著您要檢查它的確確實有所有較小的項目在左側，而較大的項目在右側。本質上，這是檢查二進制樹是否為二進制搜索樹。

我發現最好的解決方案是O（n），它不占用任何額外空間。它類似于有序遍歷，但不是將其存儲到數組中然后檢查它是否已排序，我們可以采用一個靜態變量，并在有序遍歷時檢查數組是否已排序。

static struct node *prev = NULL;

bool isBST(struct node* root)

{

    // traverse the tree in inorder fashion and keep track of prev node

    if (root)

    {

        if (!isBST(root->left))

          return false;

        // Allows only distinct valued nodes

        if (prev != NULL && root->data <= prev->data)

          return false;

        prev = root;

        return isBST(root->right);

    }

    return true;

}