具有检查树是否为BST的功能的问题

Question

因此，我有一个函数来检查树是否是bst（如果每个节点的左侧只有较小的值，而右侧则只有较大的值）。其他所有功能都起作用，而问题出在这一功能上（第二个功能只是调用辅助功能）。我认为此问题与递归调用root-left达到null有关，但我不确定，即使不确定如何解决。可以根据需要添加更多代码。任何帮助表示赞赏。

我得到的Visual Studio错误是：R00t->左边是nullptr其他编译器：分段故障核心已转储。

bool isBSThelper(TreeNode* R00t) 
{



        if (R00t == NULL)
            return true;
        //if (R00t->left != NULL && (R00t->info < R00t->left->info))
        if (R00t->info < R00t->left->info)
            return false;
        //if (R00t->right != NULL && (R00t->info < R00t->right->info))
        if (R00t->info > R00t->right->info)
            return false;

        return isBSThelper(R00t->left) && isBSThelper(R00t->right);



}

bool TreeType::isBST() const
{
    return isBSThelper(root);
}

Answer 1

根据您的评论

even with if (R00t->left != NULL || R00t->right != NULL) error persists

问题将继续存在。让我从那里重写并进行迭代（因为我无法发表评论以要求澄清-新用户）。如果您的代码是

bool isBSThelper(TreeNode* R00t) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL || R00t->right != NULL ) {
        if ( R00t->info < R00t->left->info )
            return false;
        if ( R00t->info < R00t->right->info )
            return false;
    }

    return isBSThelper(R00t->left) && isBSThelper(R00t->right);
}

然后，由于表达式，您可能仍会遇到相同的问题

if (R00t->left != NULL || R00t->right != NULL) {

仍将使用值表达该表达式

R00t->left != NULL

但是

R00t->right == NULL

评估为真。

一个解决方案可能是]

1. 要确保R00T-> left和R00t-> right是有效的（指向节点）或NULL（如果使用C ++，最好是nullptr）
2. 和这样的代码：

bool isBSThelper( TreeNode* R00t ) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL && R00t->info > R00t->left->info )
        return false;
    if ( R00t->right!= NULL && R00t->info > R00t->right->info )
        return false;

    return isBSThelper( R00t->left ) && isBSThelper( R00t->right );
}

问题就不复存在了。 （1）很关键。

附加说明：您的代码不检查

if (R00t->left != NULL && R00t->right!= NULL && R00t->left->info < R00t->right->info)
        return false;
这是二叉搜索树的另一个属性（或者在您认为合适的情况下，显然使用“>”而不是“