在这个问题中，我们给定了一个二叉树bt。我们的任务是在给定的二叉树中找到最大的二叉搜索子树。
二叉树是一种用于数据存储的特殊数据结构。二叉树有一个特殊的条件，即每个节点最多可以有两个子节点。
二叉搜索树（bst）是一棵满足以下属性的树：
左子树的键值小于其父节点（根节点）的键值。
右子树的键值大于或等于其父节点（根节点）的键值。
让我们举个例子来理解这个问题，
输入：
输出：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
以上就是在给定的二叉树中找到最大的二叉搜索子树 - c++中的第1集的详细内容。