Validate Binary Search Tree
二叉树按堆顺序存储在数组 tree 中：根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，数组末尾可能有多余的 -1 项。
编写 isValidBST，如果这棵树是二叉搜索树，则返回 true，否则返回 false。在二叉搜索树中，每个节点的值都严格大于其左子树中的所有值，并且严格小于其右子树中的所有值。
函数
- treeinteger-array
- 按层序遍历二叉树，空位置用 -1 表示
- 返回值boolean
- 如果该树是二叉搜索树，则为真；否则为假
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或满足0 ≤ tree[i] ≤ 105的值。 tree[0]永远不会是-1，所以这棵树至少有一个节点。- 数组最后一个节点之后可能还有额外的
-1项。 - 空位置的两个子节点也都是空的，并且深度最多为
14。 - 值可以重复。
示例
- 输入
- tree = [8, 3, 12, 1, 6, 10, 15]
- 输出
- true
- 解释
- 按顺序读取（左子树、节点、右子树），得到的值是
1, 3, 6, 8, 10, 12, 15。这些值严格递增，因此每个节点都位于每个祖先节点的正确一侧。
- 输入
- tree = [10, 5, 15, -1, -1, 6, 20]
- 输出
- false
- 解释
- 每个节点都大于它的左子节点，并且小于它的右子节点，但索引为
5的6位于根节点的右子树中，因此它必须大于10。
- 输入
- tree = [12, 7, 12]
- 输出
- false
- 解释
- 根节点的右子节点存储着
12，与根节点相等。右子树中的值必须严格大于根节点，因此这棵树不符合要求。
进阶
节点的父节点位于索引 (i-1)/2 处，向下取整。你能否按顺序遍历这棵树，并且只用 O(1) 的额外空间，通过父节点移动，而不使用栈或递归？
提示
逐个打开提示，每个都会多透露一点。
在
[10, 5, 15, -1, -1, 6, 20]中，每个节点都大于它的左子节点，并且小于它的右子节点。为什么它仍然不是搜索树？每个祖先都会限制一个节点的取值范围：如果节点在祖先的左侧，它就必须小于祖先；如果节点在祖先的右侧，它就必须大于祖先。这些限制共同构成一个开区间。从值
v向左走，会将上限降低到v；向右走则会将下限提高到v。维护一个由
(index, low, high)组成的栈，初始时放入根节点，并使用一个覆盖所有允许值的范围。弹出一项，如果值不严格位于范围内，就判定失败；然后将每个实际存在的子节点及其收紧后的范围压入栈中。
题解
这条规则适用于整个子树，因此只比较每个节点和它的两个子节点是不够的：深处的节点可能会违反几层之上某个祖先设定的限制。你可以按顺序遍历这棵树，并检查值是否严格递增；也可以把祖先允许的范围传给每个节点。
将每个节点与其整个子树进行比较
思路
当节点左侧的最大值小于 v 时，左侧的每个值都小于 v；当节点右侧的最小值大于 v 时，右侧的每个值都大于 v。两个递归辅助函数会找出这些值。空的一侧会返回 -1 或 100001，它们都在值的范围之外，因此不会导致检查失败。
对于每个祖先节点，都会扫描其下的每个节点一次。对于深度为 h 的树，大约会访问 n × h 次。深度最多为 14 时，这种做法开销很小；但如果树是一条包含 n 个节点的路径，开销就会增长到 O(n²)。
算法
- 遍历每个值不为
-1的索引i。 - 找到左子树
2*i+1中的最大值（如果为空，则为-1），以及右子树2*i+2中的最小值（如果为空，则为100001）。 - 如果最大值大于或等于
tree[i]，或者最小值小于或等于tree[i]，则返回false。 - 返回
true。
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return True中序遍历的值必须严格递增
思路
中序遍历会先访问左子树，然后访问节点，最后访问右子树，因此在二叉搜索树中，它会按排序顺序读取各个值。
反过来也成立。对于任意节点 v，它的整棵左子树都紧挨着排在它前面，它的整棵右子树都紧挨着排在它后面。如果序列严格递增，那么 v 前面的每个值都比它小，后面的每个值都比它大，因此这个规则对 v 以及其他每个节点都成立。
第二个示例读出的序列是 5, 10, 6, 15, 20：从 10 降到 6，就能发现放错位置的节点。每个节点只访问一次：时间复杂度为 O(n)，列表需要 O(n) 的空间。
算法
- 编写
walk(i)：如果位置为空，就停止；否则遍历2*i+1，追加tree[i]，然后遍历2*i+2。 - 调用
walk(0)，按顺序收集这些值。 - 对于从
1开始的每个位置k，如果values[k-1] ≥ values[k]，就返回false。 - 返回
true。
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return True将允许范围向下传递到树中
思路
每个祖先都会对节点施加一个限制：如果节点位于某个值为 a 的祖先的左子树中，它的值必须小于 a；如果位于右子树中，它的值必须大于 a。这些限制共同形成一个开区间 (low, high)，当且仅当节点的值严格位于区间内时，它才处于正确位置。
向下遍历时逐步构建区间。左子节点保留 low，并将 high = v；右子节点保留 high，并将 low = v。在第二个示例中，15 将 (10, 15) 传给它的左子节点，而 6 会立即失败。值的范围是 0 到 10^5，因此 -1 和 100001 可用作无限制的边界。每个节点只检查一次，时间复杂度为 O(n)，栈上有 O(h) 个节点。
算法
- 将
(0, -1, 100001)入栈：这是根节点，没有实际的边界限制。 - 弹出
(i, low, high)。如果tree[i]不严格位于low和high之间，则返回false。 - 将每个实际存在的子节点入栈：左子节点位于
2*i+1，对应(low, tree[i])；右子节点位于2*i+2，对应(tree[i], high)。 - 栈为空时，返回
true。
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
易错点和边界情况
- 只将节点与其子节点进行比较。在
[10, 5, 15, -1, -1, 6, 20]中，每对父节点和子节点看起来都没问题，但6超出了根节点的限制。 - 允许值相等。
[12, 7, 12]无效：要使用<进行比较，不能使用≤。 - 将
0用作“无下限”。这样会拒绝有效的树[0]。 - 读取子节点时没有检查
2*i+1 < tree.length。在[12, 7, 12]中，索引3超出了末尾。 - 在 Lua 和 R 中，数组从 1 开始。节点索引仍使用从 0 开始的方式来计算
2*i+1，并读取tree[i + 1]。
常见问题3
验证二叉搜索树的时间复杂度是多少？
中序检查和范围检查都会访问每个节点一次：时间复杂度为 O(n)，对于深度为 h 的树，范围检查的栈需要额外的 O(h) 空间。将每个节点与它的整个子树进行比较，成本为 O(n × h)；对于形状像路径的树，复杂度会达到 O(n²)。
你能在不存储每个值的情况下，通过中序遍历验证 BST 吗？
是的。检查只会将每个值与它前面的值进行比较，所以用一个变量保存前一个值，而不是用列表；一旦某个值不比前一个值大，就立即返回 false。额外空间降至递归或栈所需的 O(h)。
二叉搜索树可以包含重复值吗？
按照这里使用的严格定义，不允许相等的值出现在任一侧。有些教材允许相等的值出现在某一侧，例如右侧。按照这种规则，其中一个严格比较会变成 ≤。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isValidBST(tree):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [8, 3, 12, 1, 6, 10, 15]
预期输出
true