每天一道LeetCode题——验证二叉搜索树

前言

最近工作比较忙（lan） ,无论是刷题还是解析题目都停滞了。LeetCode在举办每日一题的打卡活动，刚好借着这个活动重新开始刷题。

围观我刷题的Github地址:https://github.com/JohnTsaiAndroid/KotlinLeetCode
欢迎各位star，watch，fork(~~素质三连~~

题目

98. 验证二叉搜索树

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

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

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

解法

在解题之前，先熟悉一下二叉搜索树的相关概念吧。

二叉搜索树：又叫二叉查找树，或者有序二叉树。是指一棵空树或者具有以下特征的二叉树：

1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2.若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；

3.任意节点的左、右子树也分别为二叉查找树；

二叉搜索树

看到二叉搜索树的第3点特征，我们不难想到可以用递归法来解题。但需要注意一点：也就是第1点，第2点中着重标记的文字：均小于，均大于等于

分析上图：

1. 当前节点是8: 左节点必须小于8，右节点必须大于或等于8
2. 分析8的左子节点3：除了它的左右子节点必须满足要求外，它的值还必须小于父节点的值8
3. 分析3的右节点6: 除了它的左右子节点必须满足要求外，它的值还必须大于父节点的值3，同时小于8

由上述3步可以推导出：
除了根节点外，其他子节点的值除了满足左小右大的原则外，还需要满足小于上界或大于下界的要求
（在上面讲二叉搜索树的概念提到了：均大于或均小于）。

伪代码如下：

if 当前节点 为空
  then true
if 当前节点的值 >= 上界 或 < 下界
  then false
if 左子节点不是二叉搜索树 或 右子节点不是二叉搜索树
  then false
then true

kotlin代码实现如下：

/*
 * Created by johntsai on 2020/5/5
 */
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return helper(root, null, null)
    }

    /**
     * root 待检测的节点
     * upper: 上界值
     * lower: 下界值
     */
    private fun helper(root: TreeNode?, upper: Int?, lower: Int?): Boolean {
        if (root == null) { //空节点是二叉搜索树
            return true
        }

        if (upper != null && root.`val` >= upper) {//若有上界，当前节点的值必须小于上界
            return false
        }
        if (lower != null && root.`val` <= lower) {//同理，当前节点的值必须大于下界
            return false
        }
        if (!helper(root.left, root.`val`, lower)) {//左子节点也必须是二叉搜索树
            return false
        }
        if (!helper(root.right, upper, root.`val`)) {//同理，右子节点也是
            return false
        }
        return true
    }
}