二叉树中最大的 BST

二叉树的每个子节点仅由两个节点（左子节点和右子节点）组成。数据仅通过树的拓扑结构表示。遵循这些标准的二叉树（BST）的特例包括：

• 左子节点小于父节点
• 右子节点的父节点大于子节点。

考虑一种情况，要求我们找出二叉树中最大的二叉搜索树（BST）。

在这项工作中，我们将开发一种方法来识别二叉树中最大的 BST。当二叉树是 BST 时，可以计算出整个二叉树的大小。

创建一个函数，该函数接受一个二叉树作为输入，并返回最大的子树（也称为二叉搜索树 BST）的大小。如果整个二叉树是 BST，则返回整个树的大小。

实例

C 代码

输出

Size of the largest BST is 2

• 时间复杂度：O(n)
• 空间复杂度：O(n)，因为递归使用了调用栈。

结论

在本课程中，我们学习了什么是二叉树和二叉搜索树，以及如何使用递归来识别给定二叉树中最大的 BST。将使用递归来确定每个节点下的子树是否为 BST，并相应地返回数值。