Leetcode做题日记：98. 验证二叉搜索树(PYTHON)

157 阅读 0 评论 104 点赞

我是靠谱客的博主含蓄星星，这篇文章主要介绍Leetcode做题日记：98. 验证二叉搜索树(PYTHON)，现在分享给大家，希望可以做个参考。

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

复制代码

1
2
3
4
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
2
/
1 3
输出: true

示例 2:

输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

第一次的代码：
希望递归来做，然而错了。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	def v(root):#root,tempval,maxval,minval
if not root :
return True,0,0,0
if not root.left and not root.right:
return True,root.val,root.val,root.val
tpv=root.val
l,tpl,lm,ln=v(root.left)
r,tpr,rm,rn=v(root.right)
if lm>=tpv or (tpv>=rm and root.val!=0):
return False,tpv,max(lm,tpv,rm),min(tpv,ln,rn)
if
tpv>=rn and root.val!=0:
return False,tpv,max(lm,tpv,rm),min(tpv,ln,rn)
if tpl>=tpv or (tpv>=tpr and root.val!=0):
return False,tpv,max(lm,tpv,rm),min(tpv,ln,rn)
if l and r :
return True,tpr,rm,ln
return False,tpv,max(lm,tpv,rm),min(tpv,ln,rn)
ans,tpv,mv,nv=v(root)
return ans

[34,-6,null,-21]居然是正确的，左子树都大于节点值了。

第二次代码：
当然也可以修改为中序遍历：

复制代码

1
2
3
4
5
6
7
8
9
	def v(s):
if not s:
return []
return v(s.left)+[s.val]+v(s.right) #递归中序遍历
m=v(root)
for i in range(len(m)):
if i<len(m)-1 and m[i]>=m[i+1]:#若不满足不等式则返回False
return False
return True