博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
验证二叉搜索树的golang实现
阅读量:5791 次
发布时间:2019-06-18

本文共 714 字,大约阅读时间需要 2 分钟。

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
输入:    2   / \  1   3输出: true输入:    5   / \  1   4     / \    3   6输出: false解释: 输入为: [5,1,4,null,null,3,6]。     根节点的值为 5 ,但是其右子节点值为 4 。

我们只要判断每个子树中的左孩子小于根节点,右孩子大于根节点

还有一个要注意的是,空树也是二叉搜索树

func isValidBST(root *TreeNode) bool {    return isValid(root, math.MinInt64, math.MaxInt64)}func isValid(root *TreeNode, min int, max int) bool {    if root == nil {        return true    }    if root.Val <= min {        return false    }    if root.Val >= max {        return false    }    return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)}

 

转载于:https://www.cnblogs.com/TimLiuDream/p/10128049.html

你可能感兴趣的文章
Java判断是否为垃圾_Java GC如何判断对象是否为垃圾
查看>>
多项式前k项和java_多项式朴素贝叶斯softmax改变
查看>>
oracle体系结构
查看>>
XP 安装ORACLE
查看>>
八、 vSphere 6.7 U1(八):分布式交换机配置(vMotion迁移网段)
查看>>
我的友情链接
查看>>
JS中比较数字大小
查看>>
jQuery插件的开发
查看>>
基础,基础,还是基础之JAVA基础
查看>>
JS prototype 属性
查看>>
HTTP库Axios
查看>>
gen already exists but is not a source folder. Convert to a source folder or rename it 的解决办法...
查看>>
20个Linux服务器性能调优技巧
查看>>
填坑记:Uncaught RangeError: Maximum call stack size exceeded
查看>>
SpringCloud之消息总线(Spring Cloud Bus)(八)
查看>>
【348天】每日项目总结系列086(2018.01.19)
查看>>
【294天】我爱刷题系列053(2017.11.26)
查看>>
可替换元素和非可替换元素
查看>>
2016/08/25 The Secret Assumption of Agile
查看>>
(Portal 开发读书笔记)Portlet间交互-PortletSession
查看>>