题目:98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/
2 3
Binary tree [1,2,3], return false.

1,利用二叉排序树中序遍历是递增的性质

如果中序遍历得到的结果是递增的,那么他就是一个二叉排序树
否则,则不是

public class Solution {
    //利用二叉排序树中序遍历是递增的
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        
        int curVal = Integer.MIN_VALUE;
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while(!stack.empty() || node != null){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            
            node = stack.pop();
            if(!result.isEmpty() && node.val <= curVal){
                return false;
            }
            result.add(node.val);
            curVal = node.val;
            node = node.right;
           
        }
        
        if(result.size() == 1){
            return true;
        }
        return result.get(0) < result.get(1);
    }
}

2,利用二叉排序树的定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}