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

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

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

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

示例 1:

输入:
2
/
1 3
输出: true

示例 2:

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

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

	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]居然是正确的，左子树都大于节点值了。

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

	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

76ms，排名16%
未完待续

最后

以上就是含蓄星星最近收集整理的关于Leetcode做题日记：98. 验证二叉搜索树(PYTHON)的全部内容，更多相关Leetcode做题日记：98.内容请搜索靠谱客的其他文章。