如何判断一棵二叉树是不是 BST？

Question

我正在尝试确定二叉树是否是 BST。我的想法是在进行中序遍历时，如果数据已排序，则它是 BST，否则不是。所以这就是为什么在进行中序遍历时我将值插入向量中的原因。然后检查它是否已排序。如果排序则 return true 否则 return 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

有一个更简单的方法。编写一个函数来检查给定子树是否为 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 all nodes in the left subtree is less than current node
        && checkBST(current->left, low, current->roll - 1)
        // Check if all nodes in the right subtree is greater than current node
        && checkBST(current->right, current->roll + 1, high);
}

如何判断一棵二叉树是不是 BST？

How to check a binary tree is BST or not?

c++

binary-search-tree