c++ - 给定二叉树是否为二叉搜索树

Question

我编写了一个函数，如果给定的二叉树是二叉搜索树，则返回 true，否则返回 false。

bool IsBst(node* root)
{
    if(root->left == NULL && root->right == NULL)
    {
        return true;
    }
    if(root->left->data <= root->data && root->right->data > root->data)
    {
        return (IsBst(root->left) && IsBst(root->right))
    }
    else
    {
        else false;
    }
}

我的功能对吗？

这个函数会返回正确答案吗？

我怀疑如果 left child 为 null 那么这个比较会是什么 root->left->data<=root->data return?(如果有NULL)

帮我改进一下! 提前致谢!

Answer 1

应该是这样的

bool IsBst(const node* root, node* minNode = nullptr, node* maxNode = nullptr)
{
    if (root == nullptr) {
        return true;
    }
    if (minNode != nullptr && root->data < minNode->data)
    {
        return false;
    }
    if (maxNode != nullptr && maxNode->data < root->data)
    {
        return false;
    }
    return IsBst(root->left, minNode, root)
        && IsBst(root->right, root, maxNode);
}