c++ - 如何检查一棵树是否是 BST？

Question

我必须检查一棵树是否是二叉搜索树。我正在使用一个收集值的临时数组进行中序遍历。我必须检查数组是否按升序排列，如果是，则返回 true:

bool myisBST(Node* node, std::vector<int> v);

bool myisBST(Node* node)
{
    return myisBST(node, std::vector<int>());
}

bool myisBST(Node* node, std::vector<int> v)
{
    if (node)
    {
        if (node->left)
            return myisBST(node->left, v);

        v.push_back(node->data);

        if (node->right)
            return myisBST(node->right, v);
    }

    return std::is_sorted(v.begin(), v.end());
}

当二叉树是这样的:

            50
           /  \
         25    75
        /  \   / \
       1   12 62 -99

如您所见，-99 使这不是一个二叉搜索树，但它仍然返回 true。我的实现有问题吗？

Demo

Answer 1

两个问题:

1. 在 myisBST ，你正在传递 v按值，而不是按引用，因此当您递归传递 vector 时，对其所做的更改不会更改其在调用方法中的值。只需将函数签名更改为 bool myisBST(Node* node, std::vector<int>& v)解决这个问题。
2. 您应该返回的值是 vector 是否已排序(就像您在方法的最后一行中所做的那样)，但是您通过编写 return myisBST(node->left, v); 过早地返回了和 return myisBST(node->right, v); .您实际上对这些方法的返回值不感兴趣；你只是用它们来按顺序填充 vector 。删除 return来自这两行。

在这两个修复之后，您的方法有效。