98. 验证二叉搜索树

题目描述

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

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

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

示例：

输入:
    2
   / \
  1   3
输出: true

递归思路

1.二叉搜索树的性质是根节点的左子树都比根节点小，根节点的右子树都比根节点大。
2.给每个节点设置最大值和最小值，若符合该节点值在合法区间内，则对其子节点继续递归，递归出口为节点为NULL。

Java代码实现

   public boolean isValidBST(TreeNode root) {
        return isValidBST(root,null,null);
    }

    private boolean isValidBST(TreeNode root,Integer min,Integer max) {
        if(root == null)
            return true;
        int val = root.val;
        if((min != null && val <= min) || (max != null && val >= max))
            return false;
        return isValidBST(root.left,min,val) && isValidBST(root.right,val,max);
    }

中序遍历思路

1.二叉搜索数还有一个重要的性质是，中序遍历得到的结果是一个递增序列。

Java代码实现

    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack();

        Integer min = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if(min != null && node.val <= min)
                return false;
            min = node.val;
            root = node.right;
        }

        return true;
    }