四川盐亭网站制作公司

python中如何验证二叉搜索树

这篇文章给大家介绍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中如何验证二叉搜索树就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。


网站栏目：python中如何验证二叉搜索树
URL地址：http://scyanting.com/article/iioesg.html

其他资讯