我必须检查一棵树是否是二叉搜索树。我正在使用临时数组遍历此遍历，该临时数组收集值。我必须检查数组是否升序，如果是则返回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。我的实现有问题吗？
两个问题：
myisBST，您v按值传递，而不是按引用传递，因此当递归传递向量时，对其所做的更改不会在调用方法中更改其值。只需更改功能签名bool myisBST(Node* node, std::vector<int>& v)即可解决此问题。return myisBST(node->left, v);和来过早返回return myisBST(node->right, v);。您实际上对这些方法的返回值不感兴趣。您只是使用它们来填充向量顺序。return从这两行中删除。遵循这两个修复程序，您的方法将起作用。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句