如何在二叉树中找到最大的BST

在这个问题中，我们给出了一个二叉树。我们必须找到这个给定二叉树的一个子树，它也满足被归类为二叉搜索树的要求。最后，我们必须返回给定二叉树的二叉搜索树子树的大小。我们将子树的大小定义为该树中的节点总数。让我们通过一些插图来可视化这个问题。

示例

输入

输出

5

解释： 完整的树是一个二叉搜索树。因此，二叉搜索子树的大小为 5。

输入

输出

3

这个问题中的二叉搜索子树是

因此，子树的大小是 3。

方法 - 1

在这个方法中，我们将使用最小和最大值技术来检查子树是否为二叉搜索树。一个完整的树要成为二叉搜索树的条件是，树的根节点的值应该大于左子树中最大节点的值，并且根节点的值应该小于右子树中最小节点的值。

我们将从下往上遍历树。对于遍历的每个节点，我们将存储当前根节点子树的最小值和最大值。如果当前节点符合上述讨论的属性，那么当前子树就是一棵二叉搜索树。我们将更新二叉搜索树的大小。遵循这些步骤，我们最终将返回最大二叉搜索树子树的大小。

下面是此方法的实现。

代码

输出

Tree - 1
The size of the largest BST subtree is 3
Tree - 2
The size of the largest BST subtree is 5

时间复杂度：在此程序中，我们使用 DFS 搜索来遍历二叉树；因此，时间复杂度为 O(n)

空间复杂度：我们使用了空间来存储递归栈。递归栈的空间复杂度为 O(n)。