c - 判断一棵树是否是二叉搜索树

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; 
}

Answer 1

不，这种方法是错误的，因为它会为这棵树返回一个真实的答案：

     6
    / \
   4   9
  / \
 2   10

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