C++ 在二叉树中找到最大的 BST

Question

在二叉树中拥有最大 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;
}

但实际上并没有告诉最大的。我很难做出比较。它应该如何进行？

谢谢

Answer 1

是的，你的函数 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;