检查给定大小为 n 的数组是否可以表示 n 层的 BST

问题陈述

给定一个大小为 n 的数组，你需要判断数组中的元素是否可以用来构建一个恰好有 n 层的二叉搜索树（BST）。构建过程遵循一个特定的规则来排列树中的元素。我们考虑一个数 X；

• 大于 X 的数在右侧
• 小于 X 的数在左侧。

注意：在插入一个数之前，我们绝不越过一个已经访问过的数。

示例 1

输入 500, 200, 90, 250, 100

给定的数组表示 BST 中的以下元素（假设左子节点小于父节点，右子节点大于父节点）

在这种情况下，BST 有 4 层，而不是数组中元素数量所示的 5 层。因此，输出为 "No"。

输入 5123, 3300, 783, 1111, 890

给定的数组表示 BST 中的以下元素

在这种情况下，BST 有 4 层，与数组中的元素数量相匹配。因此，输出为 "Yes"。

方法一：构建 BST 表示

该方法通过按特定顺序插入给定数组中的元素来填充树结构，这个顺序模仿了二叉搜索树（BST）的构建。每个元素根据其小于或大于前一个元素来放置。一旦树构建完成，就会进行检查以确定结果结构是否为有效的二叉搜索树。

算法

上述方法的 Java 实现

时间复杂度

构建二叉树的时间复杂度是 O(n)，其中 n 是数组中元素的数量。这是因为我们遍历数组中的每个元素一次来构建树。

检查构建的树是否为有效 BST 的时间复杂度（使用中序遍历）也是 O(n)，因为我们每个节点只访问一次。

总的来说，由于树的构建和验证是主导因素，时间复杂度为 O(n)。

空间复杂度

创建树的空间复杂度在最坏情况下是 O(n)。这是因为我们需要在树中存储数组中的所有 n 个元素。

在 BST 验证期间，递归栈的空间复杂度为 O(h)，其中 h 是树的高度。在一个平衡的 BST 中，高度 h 是 O(log n)，但在最坏情况下（倾斜树），它可以是 O(n)。

因此，总的空间复杂度是 O(max(n, h))。在最坏情况下，对于一个倾斜树，它可以是 O(n)。

方法二：使用数组

• 利用两个变量，'max' 初始化为 INT_MAX 表示左子树的上限，'min' 初始化为 INT_MIN 表示右子树的下限。从 arr[1] 到 arr[n-1] 遍历数组。
• 对数组中的每个元素，执行以下检查
• 如果当前元素（arr[i]）大于前一个元素（arr[i-1]）并且在 'min' 和 'max' 之间的范围内，则将 'min' 更新为 arr[i-1] 的值。
• 如果当前元素不大于前一个元素但仍在 'min' 和 'max' 之间的范围内，则将 'max' 更新为当前元素的值。
• 如果以上两个条件都不成立，则意味着当前元素无法插入到新的层级，因此跳出循环。

通过应用这些条件，你可以在遍历数组时有效地确定左右子树的边界

上述方法的 Java 实现

时间复杂度： 该代码的时间复杂度在最坏情况下是 O(n)，其中 'n' 是 'values' 数组中元素的数量。这是因为它遍历整个数组一次，对每个元素执行常数时间的操作。

空间复杂度： 该代码的空间复杂度是 O(1)，这意味着它使用的内存量是恒定的，与输入大小无关。它只使用了几个整型变量（'max', 'min', 'n', 'i', 'isBST'），不需要随输入大小扩展的额外内存。