在算法面试中,验证二叉搜索树(Binary Search Tree, BST)是一个既经典又富有挑战性的题目。二叉搜索树是一种特殊的二叉树,其中每个节点都遵循以下性质:节点的左子树只包含小于节点值的元素,节点的右子树只包含大于节点值的元素,且左右子树也必须是二叉搜索树。本题要求设计一个算法来验证给定的二叉树是否满足二叉搜索树的定义。
首先,我们需要明确二叉搜索树的定义,并据此设计出验证算法。直观上,我们可以遍历整棵树,并检查每个节点的值是否满足二叉搜索树的性质。然而,简单的遍历方法(如先序、中序、后序遍历)虽然能访问到所有节点,但直接利用它们来验证二叉搜索树性质并不高效。特别是,中序遍历(左-根-右)能够产生一个递增的元素序列,这是验证二叉搜索树最直观且有效的方法。
递归中序遍历验证:
非递归中序遍历验证:
利用BST性质直接判断:
以下是使用递归中序遍历验证二叉搜索树的Python代码示例:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(root, prev=float('-inf')):
# 空树是BST
if not root:
return True
# 检查左子树
if not isValidBST(root.left, prev):
return False
# 检查当前节点
if root.val <= prev:
return False
# 更新prev为当前节点值,继续检查右子树
return isValidBST(root.right, root.val)
# 调用函数验证
# 假设已有一棵二叉树root
# result = isValidBST(root)
# print(result)
接下来是非递归版本的实现,使用栈来模拟递归过程:
def isValidBSTIterative(root):
stack, prev = [], float('-inf')
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if current.val <= prev:
return False
prev = current.val
current = current.right
return True
# 调用函数验证
# result = isValidBSTIterative(root)
# print(result)
通过以上分析,我们不仅掌握了验证二叉搜索树的基本方法,还理解了其背后的算法思想和性能考量,这对于准备算法面试或解决类似问题具有重要意义。