# 0098. Validate Binary Search Tree
###### tags: `Leetcode` `Medium` `FaceBook` `Binary Search Tree` `Tree Traversal`
Link: https://leetcode.com/problems/validate-binary-search-tree/
## 思路
Recursion
中序遍历binary search tree得到的阵列单调递增
用Integer而不是int的原因是他要检查是否是strictly binary search tree, 也就是left child的值一定小于root value，right child的值一定大于root value，所以low跟high不能设成```Integer.MIN_VALUE```和```Integer.MAX_VALUE```
## Code
### 思路一 $O(N)$ $O(N)$

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkValid(root,null,null);
    }
    public boolean checkValid(TreeNode root, Integer low, Integer high){
        if(root==null) return true;
        if(low!=null&&root.val<=low){
            return false;
        }
        if(high!=null&&root.val>=high){
            return false;
        }
        return checkValid(root.left,low,root.val) && checkValid(root.right,root.val,high);
    }
}

### 思路二

class Solution {
    class ColorNode{
        TreeNode node;
        int color;
        public ColorNode(TreeNode node, int color){
            this.node = node;
            this.color = color;
        }
    }
    public boolean isValidBST(TreeNode root) {
        Integer prev = null;
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root, 0));
        while(!stack.isEmpty()){
            ColorNode cnode = stack.pop();
            if(cnode.color == 0){
                if(cnode.node.right != null) stack.push(new ColorNode(cnode.node.right,0));
                stack.push(new ColorNode(cnode.node,1));
                if(cnode.node.left != null) stack.push(new ColorNode(cnode.node.left,0));
            }
            else{
                System.out.println(prev);
                if(prev == null) prev = cnode.node.val;
                else if(prev>=cnode.node.val) return false;
                prev = cnode.node.val;
            }
        }
        return true;
    }
}