给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
复制代码
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
20def 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
9def 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.内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复