題目: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);
    }
}