在给定的二叉树中查找最大的 BST 子树 - C++ 方法一

在这个问题中，我们给定一个二叉树 BT。我们的任务是 *在给定的二叉树中找到最大的 BST 子树*。

二叉树是一种特殊的数据结构，用于数据存储。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。

二叉搜索树 (BST)是一种树，其中所有节点都遵循以下属性：

  • 左子树的键值小于其父节点（根节点）的键值。

  • 右子树的键值大于或等于其父节点（根节点）的键值。

让我们来看一个例子来理解这个问题：

输入

输出：3

解释

Full binary tree is a BST.

解决方案

解决这个问题的一个简单方法是对树进行中序遍历。对于树的每个节点，检查其子树是否是 BST。最后返回作为 BST 的最大子树的大小。

示例

程序演示了我们解决方案的工作原理

Open Compiler
#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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

The size of the largest possible BST is 5

另一种方法

解决这个问题的另一种方法是从底部遍历树，并使用其子节点检查它是否是 BST。对于这个节点，我们将跟踪：

它是否是 BST。

  • 左子树中的最大元素值。

  • 右子树中的最小元素值。这些值需要与当前节点进行比较，以检查 BST。

此外，将通过与当前 BST 大小进行比较来更新最大 BST 的大小。

示例

Open Compiler
#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

更新于：2022年1月28日

221 次查看

启动您的 职业生涯

完成课程后获得认证

开始
广告