如何判断一棵树是否为二叉搜索树

Question

这种方法用于判断树是否为BST是否正确吗？

节点的左子树仅包含键值小于该节点键值的节点。节点的右子树仅包含键值大于该节点键值的节点。而且左右子树都必须是二叉搜索树。

我的代码如下：

isBST(struct node* node) 
{ 
  if (node == NULL) 
    return 1; 
  if (node->left != NULL && node->left->data > node->data) 
    return 0; 
  if (node->right != NULL && node->right->data < node->data) 
    return 0; 
  if (!isBST(node->left) || !isBST(node->right)) 
    return 0; 
  return 1; 
}

- user2227862

---

虽然您的代码不正确（请参阅答案），但您还需要记住在其中一个检查中包括相等性（即>=或<=），取决于您希望节点相等的位置。 - Bernhard Barker

可能是如何验证二叉搜索树？的重复问题。 - Bernhard Barker

Answer 1

不，这种方法是错误的，因为它会返回这棵树的正确答案：

     6
    / \
   4   9
  / \
 2   10

虽然它不是二叉搜索树！我建议更好的方法是进行中序遍历并验证其是否实际上已排序。

- poorvank