二叉树 验证二叉搜索树 98

需求

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

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

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

注意： 二叉搜索树中序遍历，元素是有序单调递增的。

leetcode题目链接

思路

根据搜索二叉树的概念使用递归中序遍历左中右的形式更方便一些，验证完左子树验证根节点，再验证右子树节点。完成整棵树值的验证。

/**
 *
 *98. 验证二叉搜索树
 */
public class IsValidBST98 {

    Long maxVal = Long.MIN_VALUE;

    /**
     * 递归方式
     * 有些测试用例比int最小值还小
     * 如果值小于最小值直接返回false，这个实现方式会有这个问题
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (root.val > maxVal) {
            maxVal = (long) root.val;
        } else {
            return false;
        }
        boolean right = isValidBST(root.right);
        return left && right;
    }

    private TreeNode preNode = null;

    /**
     * 递归方式
     */
    public boolean isValidBST1(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (preNode ==null || root.val > preNode.val) {
            preNode = root;
        } else {
            return false;
        }
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

验证结果