❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/validate-binary-search-tree/

❞

题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

「有效」 二叉搜索树定义如下：

• 节点的左子树只包含 「小于」 当前节点的数。
• 节点的右子树只包含 「大于」 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return isValidBST2(root, math.MinInt64, math.MaxInt64)
}

func isValidBST2(root *TreeNode, minVal int, maxVal int) bool {
    if root == nil {
        return true
    }

    if root.Val >= maxVal || root.Val <= minVal {
        return false
    }

    return isValidBST2(root.Left, minVal, root.Val) && isValidBST2(root.Right, root.Val, maxVal)
    
}

复杂度分析

• 时间复杂度：, 为节点个数，每个节点都要算一次，总共是 次。
• 空间复杂度：，空间复杂度为调用栈的深度，最多为 层，即二叉树退化成链表的时候。