这篇文章给大家介绍python中如何验证二叉搜索树,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 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<root.Val && root.Val<r } if root.Left!=nil{ l:=maxBST(root.Left) return isValidBST(root.Left)&&l<root.Val } if root.Right!=nil{ r:=minBST(root.Right) return isValidBST(root.Right)&&root.Val<r } 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中如何验证二叉搜索树就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4586289/blog/4634782