如何检查二叉树是否是BST？

Question

我正在尝试确定二进制树是否是BST。我的想法是，如果对数据进行排序，则在进行有序遍历时会是BST，否则就不会。这就是为什么在进行有序遍历时将值插入向量中的原因。然后检查是否已排序。如果已排序，则返回true，否则返回false。

vector<int>vect;
void preOrder(node *current)
{
    if(current==NULL) return;

    preOrder(current->left);
    cout<<current->roll<<endl;
    vect.push_back(current->roll);
    preOrder(current->right);


}

bool checkBST(node *current)
{
    preOrder(current);
    int c=0;
    for(int i=1;i<vect.size();i++)
    {
        if(vect[i]>=vect[i-1])
        {
            continue;
        }

        else
        {
            c=1;
        }



    }

    if(c==1)
    {
        return false;
    }
    else
    {
        return true;
    }

 // cout<<c<<endl;
}

我的想法有什么问题吗？

Answer 1

您可以用更少的代码和更少的内存来实现。

bool checkBST(const node* current) // Not modifying node!
{
    // Here, empty tree is sorted in the sense that it does
    // not violate BST invariants
    if (!current) return true;

    // Left side of the tree violates ordering
    if (current->left && !(current->left->roll < current->roll))
       return false;

    // Right side of the tree violates ordering
    if (current->right && !(current->right->roll >= current->roll))
       return false;

    // Go down the tree recursively
    return checkBST(current->left) && checkBST(current->right);
}

Answer 2

有一种更简单的方法。编写一个函数，以检查给定的子树是否是BST，并且所有节点都在给定范围内。

// Checks if the tree rooted at current is a BST and
// all nodes are between low and high
bool checkBST(node* current, int low = std::numeric_limits<int>::min(),
    int high = std::numeric_limits<int>::max())
{
    // Check for empty subtree
    if (!current)
    {
        return true;
    }
    // Check if current node is in range
    return current->roll >= low && current->roll <= high
        // Check if left subtree is less than current node
        && checkBST(current->left, low, current->roll - 1)
        // Check if right subtree is greater than current node
        && checkBST(current->right, current->roll + 1, high);
}