在这个问题中，我们给定了一个二叉树bt。我们的任务是在给定的二叉树中找到最大的二叉搜索子树。
二叉树是一种用于数据存储的特殊数据结构。二叉树有一个特殊的条件，即每个节点最多可以有两个子节点。
二叉搜索树（BST）是一棵满足以下属性的树：
左子树的键值小于其父节点（根节点）的键值。
-
右子树的键值大于或等于其父节点（根节点）的键值。
立即学习“C++免费学习笔记（深入）”；
让我们举个例子来理解这个问题，
输入：
输出：3
解释
Full binary tree is a BST.
解决方案
解决问题的简单方法是对树进行中序遍历。对于树的每个节点，检查其子树是否是二叉搜索树。最后返回最大的二叉搜索子树的大小。
示例
程序示例，说明我们解决方案的工作原理
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int findTreeSize(node* node) {
if (node == NULL)
return 0;
else
return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
if (node == NULL)
return 1;
if (node->left != NULL && node->left->data > node->data)
return 0;
if (node->right != NULL && node->right->data < node->data)
return 0;
if (!isBSTree(node->left) || !isBSTree(node->right))
return 0;
return 1;
}
int findlargestBSTSize(struct node *root) {
if (isBSTree(root)){
return findTreeSize(root);
}
else
return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
return 0;
}输出
The size of the largest possible BST is 5
另一种方法
解决这个问题的另一种方法是从底部遍历树，并通过其子节点检查是否为BST。为此，我们将跟踪以下内容：
是否为BST。
在左子树的情况下，最大元素的值。
在右子树的情况下，最小元素的值。这些值需要与当前节点进行比较以检查BST。
此外，通过与当前BST的大小进行比较，最大BST的大小将得到更新。
示例
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
if (node == NULL){
*isBSTree = true;
return 0;
}
int min = INT_MAX;
bool left_flag = false;
bool right_flag = false;
int leftSubtreeSize,rightSubTreeSize;
*maxValLsubTree = INT_MIN;
leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data > *maxValLsubTree)
left_flag = true;
min = *minValRsubTree;
*minValRsubTree = INT_MAX;
rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data < *minValRsubTree)
right_flag = true;
if (min < *minValRsubTree)
*minValRsubTree = min;
if (node->data < *minValRsubTree)
*minValRsubTree = node->data;
if (node->data > *maxValLsubTree)
*maxValLsubTree = node->data;
if(left_flag && right_flag){
if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
*maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
return (leftSubtreeSize + rightSubTreeSize + 1);
}
else{
*isBSTree = false;
return 0;
}
}
int findlargestBSTSize(node* node){
int min = INT_MAX;
int max = INT_MIN;
int largestBSTSize = 0;
bool isBST = false;
findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
return largestBSTSize;
}
int main(){
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
return 0;
}输出
The Size of the largest BST is 5
