LeetCode98. 验证二叉搜索树

题目描述

/**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 假设一个二叉搜索树具有如下特征：
     * <p>
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     */

思路分析

1. 验证二叉搜索树，首先需要理解满足二叉搜索树的条件，即当前节点的左子树的所有元素的值都小于当前节点的值，当前节点的右子树的所有元素的值都大于当前节点的值，当前节点的左子树和右子树也必须是二叉搜索树
2. 定义两个变量确定一个范围，表示当前节点元素的值应该满足的范围，如果是左子树的左子节点，则应该直接小于父节点的值，如果是右子节点，则应该大于当前节点的直接父节点，而小于树的根节点
3. 如果是右子树的左子节点，则应该小于当前节点的直接父节点的值，并且大于该树根节点的值，如果是右子节点，则直接大于当前父节点的值即可
4. 编写一个递归函数实现上述功能，并向左向右递归
5. 源码见下

源码及分析

/**
     *
     * @param root 根节点
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        //初始最小最大值为Long对应的最小最大值
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 功能：判断以root为根节点的子树的左右节点是否在指定的范围
     *
     * @param root  二叉树根节点
     * @param lower 以root为根节点的满足二叉搜索树的最小值
     * @param upper 最大值
     * @return 返回判断的结果
     */
    public boolean isValidBST(TreeNode root, long lower, long upper) {
        //如果根节点为空
        if (root == null) {
            return true;
        }
        //如果当前节点的值不满足二叉搜索树的条件
        if (!(root.val > lower && root.val < upper)) {
            return false;
        }
        //向左向右递归判断
        return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
    }

LeetCode98. 验证二叉搜索树