题目

leetcode:98

代码与解析

这道题也用递归做,

二叉搜索树的几个特征

  • 节点的左子树只包含小于当前节点的数。

  • 节点的右子树只包含大于当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

但是!!!
写代码的时候不要单纯 判断当前节点大于做节点,小于右节点,这样是错的
我们要比较的是 左子树所有节点小于中间节点,右子树所有节点大于中间节点。
比如下面的这个用例


整体代码:

func isValidBST(root *TreeNode) bool {
    var traversal func(root *TreeNode, min int64, max int64)bool
    traversal = func(root *TreeNode, min int64, max int64)bool{
        if root == nil{
            return true
        }
        if min>=int64(root.Val)||max<=int64(root.Val){
            return false
        }
        return traversal(root.Left, min, int64(root.Val))&&traversal(root.Right, int64(root.Val), max)
    }
    return traversal(root, math.MinInt64, math.MaxInt64)
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72833 人次

浙公网安备33011302000604

辽ICP备20003309号