我是靠谱客的博主 含蓄星星,这篇文章主要介绍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

76ms,排名16%
未完待续

最后

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(104)

评论列表共有 0 条评论

立即
投稿
返回
顶部