经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » Go语言 » 查看文章
验证二叉搜索树的golang实现
来源:cnblogs  作者:timliudream  时间:2018/12/17 9:45:03  对本文有异议

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

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

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

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

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

  1. func isValidBST(root *TreeNode) bool {
  2. return isValid(root, math.MinInt64, math.MaxInt64)
  3. }
  4. func isValid(root *TreeNode, min int, max int) bool {
  5. if root == nil {
  6. return true
  7. }
  8. if root.Val <= min {
  9. return false
  10. }
  11. if root.Val >= max {
  12. return false
  13. }
  14. return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
  15. }

 

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号