检查二叉树是否为二叉搜索树

二叉搜索树是具有某些约束的更通用的二叉树的后代。在二叉搜索树中，节点的排列应遵循一定的属性。这些属性是

• 树的所有父节点的值都应大于左子树的子节点。
• 所有父节点的值都应小于右子树的子节点。

每个节点的左右子树也应遵循上述二叉搜索树的两项属性。

二叉搜索树不包含任何重复值。

在本教程中，我们将通过不同的方法查看二叉树是否为二叉搜索树。我们将探讨各种可能的解决方案。

方法 - 1

解决此问题的最基本思想是检查每个节点，看左子树中的节点是否小于父节点，右子树中的节点是否大于父节点。我们将使用递归函数来解决此问题。

以下是解决问题的算法方法

• 首先，我们将说明基本条件，即如果树的当前节点为空或为 null，我们将返回 true。空节点是二叉搜索树。
• 然后我们将检查左子节点。如果当前父节点的值小于或等于（二叉搜索树应具有不同的元素）左子树中子节点的值，我们将返回 false。
• 下一步是检查右子树的条件。如果当前父节点的值大于或等于右子树中子节点的值，我们将返回 false。
• 然后我们将递归调用当前节点的左右子树的函数。如果任何函数调用返回 false，我们将返回 false。
• 如果函数到达这一点，则表示所有条件都已满足，该二叉树是二叉搜索树。因此，我们将返回 true。

以下是上述方法的 Python 代码。

代码

输出

The given tree is a BST

时间复杂度：此方法的 O(N²) 是时间复杂度。时间复杂度是非线性的，因为检查二叉树条件的函数会访问每个节点；因此，O(N)，并且返回最小和最大值的函数也会访问每个节点，需要 O(N) 时间。因此，最终时间复杂度为 O(N) * O(N) = O(N^2)。

空间复杂度：空间复杂度为 O(H)。这里 H 表示给定二叉树的高度。此额外空间由递归堆栈占用。

方法 - 2

此方法的核心思想是创建一个函数，该函数将接收节点、最小值和最大值。此函数将从上到下遍历树，跟踪节点值应存在的范围。每次都会更新最小值和最大值，以便我们可以检查二叉树是否符合二叉搜索树的条件。此方法只会访问每个节点一次。min_val 和 max_val 的初始值应为节点可能拥有的最小和最大整数。这将是根节点的范围，因为根节点可以保存任何值。每次迭代后，左右子树的范围将相应地缩小。

如果树包含具有 min_val 和 max_val 的重复元素，则无法使用此方法。

这是解决问题的算法方法：

• 我们将在主函数中调用辅助函数 isBST()。我们将向该函数提供根节点、min_val 和 max_val，即最小和最大整数值。
• 如果当前节点为 None，则函数将返回 True
• 如果当前节点允许的最小值大于节点值，或者反之，如果当前节点的值大于它可以拥有的最大值，则函数将返回 False
• 然后我们将递归地为左子树和右子树调用此函数。但现在我们必须更改左右子树的 min_val 和 max_val 的值。我们将在代码中了解如何更改这些值。

以上方法的实现如下：

代码

输出

The given tree is a BST

时间复杂度：此方法具有线性时间复杂度，即 O(N)。这里 N 是二叉树中的节点数。

空间复杂度：程序将占用 O(H)。需要空间来存储递归函数堆栈。

使用中序遍历检查二叉树是否为二叉搜索树

此方法将使用中序遍历来确定给定的二叉树是否为二叉搜索树。二叉搜索树的中序遍历遵循一个属性。该属性是二叉搜索树的中序遍历列表始终按升序排列，这是因为 BST 中节点的排列。因此，我们将执行中序遍历，然后检查输出是否按升序排列。如果输出不是升序，则给定的二叉树不是二叉搜索树。

以下是使用上述方法解决问题的算法方法

• 首先，我们将执行给定二叉树的中序遍历。我们将此输出存储在数组中。
• 我们假设二叉树不包含任何重复值。
• 接下来，我们将运行一个循环来检查输出数组中的元素是否按升序排列。

代码

输出

The given tree is a BST

时间复杂度：此方法也具有线性时间复杂度，即 O(N)，其中 N 是树中的节点数

空间复杂度：程序将占用 O(H)。需要空间来存储递归函数堆栈。

我们可以通过不创建数组来进一步减小空间复杂度。我们可以跟踪最后一个元素，并检查当前节点值是否大于前一个节点值。如果不是，我们将停止循环并返回 False。如果循环完成，则该二叉树是二叉搜索树。

代码

输出

The given tree is a BST

使用莫里斯遍历查找二叉树是否为二叉搜索树

以下是使用莫里斯遍历解决问题的算法方法

• 首先，我们将检查当前节点是否为 null。如果当前节点不为 null，我们将继续进行。
• 我们将检查当前节点是否有左子节点。如果没有左子节点，我们将处理当前节点并移至当前节点的右子节点。
  • 但是，如果当前节点包含左子节点，那么我们将找到该节点的**中序前驱**。中序前驱是位于左子树最右位置的节点。然后我们将检查中序前驱的值是否小于当前父节点的值。
• 如果中序前驱的右子节点为 null，那么我们将将其指针设置为当前节点，并继续处理当前父节点的左子节点。
  • 但是，如果中序前驱的右子节点指向当前节点，那么我们将将其设置为 null。这样做是为了恢复给定二叉树的原始结构。我们将处理父节点，然后移至右子节点。
• 我们将迭代地重复上述步骤，直到我们到达树的末尾并且当前节点为 null。
• 如果在不中断的情况下完成循环，则二叉搜索树定律未被违反，给定的树是二叉搜索树。

以下是上述方法的 Python 代码

代码

输出

The binary tree is a valid BST