重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章给大家介绍python中如何验证二叉搜索树,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
创新互联公司服务紧随时代发展步伐,进行技术革新和技术进步,经过10多年的发展和积累,已经汇集了一批资深网站策划师、设计师、专业的网站实施团队以及高素质售后服务人员,并且完全形成了一套成熟的业务流程,能够完全依照客户要求对网站进行做网站、成都网站设计、建设、维护、更新和改版,实现客户网站对外宣传展示的首要目的,并为客户企业品牌互联网化提供全面的解决方案。
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
解题思路:
1,中序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */var last=^(int(^uint(0) >> 1))func isValidBST(root *TreeNode) bool { if root!=nil{ if!isValidBST(root.Left){ return false } if last>=root.Val{ return false } last=root.Val if !isValidBST(root.Right){ return false } } return true}
方法二:
递归:根节点>大于左节点最大值,小于右节点最小值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
if root==nil{
return true
}
if root.Left!=nil&& root.Right!=nil{
l:=maxBST(root.Left)
r:=minBST(root.Right)
return isValidBST(root.Left)&&isValidBST(root.Right)&&l
}
if root.Left!=nil{
l:=maxBST(root.Left)
return isValidBST(root.Left)&&l
}
if root.Right!=nil{
r:=minBST(root.Right)
return isValidBST(root.Right)&&root.Val
}
return true
}
func maxBST(root *TreeNode)int{
if root.Right!=nil{
return maxBST(root.Right)
}
return root.Val
}
func minBST(root *TreeNode)int{
if root.Left!=nil{
return minBST(root.Left)
}
return root.Val
}
关于python中如何验证二叉搜索树就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。