98. 验证二叉搜索树
方法一：中序遍历
二叉搜索树（二叉排序树、二叉查找树）（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树；若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
二叉搜索树中序遍历得到的序列一定是严格递增序列。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def inorder(node):
return inorder(node.left) + [node.val] + inorder(node.right) if node else []
x = inorder(root)
for i in range(1,len(x)):
if x[i] <= x[i-1]:
return False
return True
方法二：中序遍历
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack, inorder = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= inorder:
return False
inorder = root.val
root = root.right
return True
方法三：递归
设计一个递归函数
h
e
l
p
e
r
(
r
o
o
t
,
l
o
w
e
r
,
u
p
p
e
r
)
helper(root, lower, upper)
helper(root,lower,upper)，表示以
r
o
o
t
root
root 为根的子树，判断子树中所有节点的值是否都在开区间
(
l
o
w
e
r
,
u
p
p
e
r
)
(lower,upper)
(lower,upper) 内。
如果
r
o
o
t
root
root 节点的值
v
a
l
val
val 不在
(
l
o
w
e
r
,
u
p
p
e
r
)
(lower,upper)
(lower,upper) 内直接返回 False，否则继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
根据二叉搜索树的性质，在递归调用左子树时，把上界
u
p
p
e
r
upper
upper 改为
r
o
o
t
.
v
a
l
root.val
root.val，即调用
h
e
l
p
e
r
(
r
o
o
t
.
l
e
f
t
,
l
o
w
e
r
,
r
o
o
t
.
v
a
l
)
helper(root.left, lower, root.val)
helper(root.left,lower,root.val)。递归调用右子树时，把下界
l
o
w
e
r
lower
lower 改为
r
o
o
t
.
v
a
l
root.val
root.val，即调用
h
e
l
p
e
r
(
r
o
o
t
.
r
i
g
h
t
,
r
o
o
t
.
v
a
l
,
u
p
p
e
r
)
helper(root.right, root.val, upper)
helper(root.right,root.val,upper)。
函数递归调用的入口为
h
e
l
p
e
r
(
r
o
o
t
,
?
i
n
f
,
+
i
n
f
)
helper(root, -inf, +inf)
helper(root,?inf,+inf)。
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:
if not node: return True
val = node.val
if val <= lower or val >= upper: return False
if not helper(node.right, val, upper): return False
if not helper(node.left, lower, val): return False
return True
return helper(root)
|