python中如何验证二叉搜索树

发布时间:2021-12-13 16:21:04 作者:柒染
来源:亿速云 阅读:212

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

推荐阅读:
  1. python中如何爬取12306验证码
  2. python中如何生成验证码

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python 二叉树

上一篇:docker怎么推送images到自己的docker hub

下一篇:Docker容器创建、启动、和停止的方法是什么

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》