LeetCode 0098.验证二叉搜索树

验证二叉搜索树

LeetCode98. 验证二叉搜索树

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

假设一个二叉搜索树具有如下特征：

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

思路

中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了

确定递归函数的参数和返回值
- 参数：要定义一个longlong的全局变量，用来比较遍历的节点是否有序，因为后台测试数据中有int最小值，所以要定义为longlong的类型，初始化为longlong最小值
- 返回值：只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值
终止条件：若为空节点，则直接返回true
确定单层递归逻辑
- 分别对左子树和右子树递归判断，如果左子树和右子树都符合则返回true，一直更新minVal或maxVal，一旦发现minVal >= node.Val或max <= node.Val，就返回false，注意元素相同时候也要返回false

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func isValidBST(root *TreeNode) bool {
    // 二叉搜索树也可以是空树
    if root == nil {
        return true
    }
    // 由题目中的数据限制可以得出min和max
    return check(root, math.MinInt64, math.MaxInt64)
}

func check(node *TreeNode, min, max int64) bool {
    if node == nil {
        return true
    }

    if min >= int64(node.Val) || max <= int64(node.Val) {
        return false
    }
    // 分别对左子树和右子树递归判断，如果左子树和右子树都符合则返回true
    return check(node.Right, int64(node.Val), max) && check(node.Left, min, int64(node.Val))
}

Link

GitHub