在C++中，将二叉树中的最大二叉搜索树（Largest BST in a Binary Tree）进行翻译-C++-PHP中文网

在C++中，将二叉树中的最大二叉搜索树（Largest BST in a Binary Tree）进行翻译

PHPz

发布： 2023-09-13 16:29:04

转载

882 人浏览过

在C++中，将二叉树中的最大二叉搜索树（Largest BST in a Binary Tree）进行翻译

在二叉树中，每个子节点只有两个节点（左和右）。树结构只是数据的表示。二叉搜索树（BST）是满足这些条件的特殊类型的二叉树 -

与其父节点相比，左子节点较小
右子节点的父节点比子节点大

假设给定一棵二叉树，我们有应该找出其中最大的二叉搜索树 (BST)。

在此任务中，我们将创建一个函数来查找二叉树中最大的 BST。当二叉树本身是BST时，就可以确定整个二叉树的大小。举个例子 -

输入

登录后复制

如图所示，在本例中突出显示的 BST 子树是最大的。 '3' 是子树的大小，因此返回值是子树的大小。

输入

    52
    / \
   37 67
   /\ / \
 12 27 57 77
          /\
         72 87

登录后复制

输出

登录后复制

节点长度小于其父节点长度的子树最多具有三个大小的 BST 节点。

查找给定二叉树中最大 BST 的方法

对于每个节点 x，如果以下点有效，则二叉树是 BST。只有数据小于其父节点数据的节点才会出现在节点的左子树中。只能有一个节点比其父节点拥有更多数据。左子树和右子树都应该用二叉搜索树（BST）来表征。

算法将是 -

我们将从二叉树并使用递归进行中序遍历。对于当前节点“ROOT”，我们将执行以下操作 -

如果它是有效 BST 的根，我们将返回其大小。
否则，我们将在左右子树中找到最大的 BST。

示例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      return true;
   }
   if (root->data < min || root->data > max) {
      return false;
   }
   return isBST (root->left, min, root->data - 1) &&
   isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
   if (root == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct Node *root = newNode (67);
   root->left = newNode (72);
   root->right = newNode (77); root->left->left = newNode (57);
   printf ("Size of the largest BST is %d", largestBST (root));
   return 0;
}

登录后复制