给定的二叉树是有效的BST吗？
给定的二叉树是有效的BST吗？
提问于 2019-06-12 13:29:51
如果树是BST。那么有序遍历必须给我们一个排序的数组。如果数组是排序的，那么给定的树一定是BST，那么为什么这段代码会失败
提前感谢
void getInorder(vector<int> &inorder, TreeNode* A){
if(A == NULL)
return;
getInorder(inorder,A->left);
//cout<<A->val<<" ";
inorder.push_back(A->val);
getInorder(inorder,A->right);
}
int Solution::isValidBST(TreeNode* A) {
//If it is a valid BST //Then its inorder Must be a sorted array;
vector<int> inorder;
if(A == NULL)
return 0;
getInorder(inorder,A);
// for(int a:inorder)
// cout<<a<<" ";
cout<<endl;
return is_sorted(inorder.begin(), inorder.end()) == true ? 1 : 0;
}输出1:是BST，0:不是BST
Failing Test Case :
2
/ \
1 2其InOrder遍历为: 1,2,2 (已排序) MyCode O/P :1，预期O/P :0
原因：(它不是BST，因为Right Sub tree必须有一个大于Root的值，在本例中等于root)
如果重复的值按某种顺序出现，它将失败。
回答 1
Stack Overflow用户
发布于 2019-06-15 08:55:31
问题是{1, 2, 2}实际上是一个排序列表。因此，对于这样的数组，std::is_sorted返回true。下面是一个小示例，供您试用：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> mtmd = {1, 2, 3, 4, 5, 5};
std::cout << std::is_sorted(mtmd.begin(), mtmd.end()) << std::endl;
}输出是true，应该是。最好的解决方案是实现您自己的is_sorted。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56555215
复制相关文章
相似问题
腾讯云开发者
