在二叉树中拥有最大 BST 的方法是什么?最大,我的意思是:最高。
我指的是 this post查找树是否存在的一个很好的实现 BST与否是
bool isBinarySearchTree(BinaryTree * n,
int min=std::numeric_limits<int>::min(),
int max=std::numeric_limits<int>::max())
{
return !n || (min < n->value && n->value < max
&& isBinarySearchTree(n->l, min, n->value)
&& isBinarySearchTree(n->r, n->value, max));
}
很容易实现一个解决方案来查找一棵树是否包含二叉搜索树。我认为以下方法可以做到:
bool includeSomeBST(BinaryTree* n)
{
return includeSomeBST(n->left) || includeSomeBST(n->right) ;
if(n == NULL)
return false ;
return true ;
}
但是如果我想要最大的 BST 怎么办?这是我的第一个想法,
BinaryTree largestBST(BinaryTree* n)
{
if(isBinarySearchTree(n))
return n;
if(!isBinarySearchTree(n->left))
{
if(!isBinarySearchTree(n->right))
if(includeSomeBST(n->right))
return largestBST(n->right);
else if(includeSomeBST(n->left))
return largestBST(n->left);
else
return NULL;
else
return n->right;
}
else
return n->left;
}
但实际上并没有告诉最大的。我很难做出比较。它应该如何进行?
谢谢
最佳答案
是的,你的函数 includeSomeBST 是错误的。您只需检查节点 n,n->left 和 n->right,但您必须递归地检查节点。
bool includeSomeBST(BinaryTree* n) {
if(!isBinarySearchTree(n))
{
return includeSomeBST(n->left) || includeSomeBST(n->right);
}
if(n==NULL) return false;
return true;
关于C++ 在二叉树中找到最大的 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12767651/