98. Validate Binary Search Tree

一开始in-order traverse
然后加入到STACK里，最后一个一个POP STACK里的元素，POP出就和堆顶比较，不大于就说明不符合规定。
AC了，不过7MS。问题在于必须遍历一次，然后再重新遍历STACK，可能提前结束判断。
需要一个在遍历时一旦发现不符合规定直接停止的办法。

其实还是in-order traverse,只不过要记录prev
NODE用于比较。

TreeNode prev = null;
    public boolean isValidBST(TreeNode root) 
    {
        if( root == null) return true;
        if(!isValidBST(root.left)) return false;
        if(prev != null && prev.val >= root.val) return false;
        prev = root;
        if(!isValidBST(root.right)) return false;
        
        return true;
    }

prev相当于栈顶元素，比较如果不满足直接就可以RETURN FALSE，提前结束。

二刷。

一看知道是in-order traversal来判断，用一个全局变量来标记上一个NODE的VALUE。

一开始全局变量用的int,初始 Integer.MIN_VALUE。
结果发现TEST CASE里面各种
[-2147483648,-2147483648]
[-2147483648]
[2147483647,null,-2147483648]
这样的。。

设计的这个的人素质也太差了。。。诚心搞我呀。

全局变量换成NODE就行了，其实一开始用MIN_VALUE主要就是为了第一次判断不出错，用NULL更好。

public class Solution 
{
    public TreeNode temp = null;

    public boolean isValidBST(TreeNode root) 
    {
        if(root == null) return true;
        if(isValidBST(root.left))
        {
            if(temp == null || temp.val < root.val)
            {
                temp = root;
                return (isValidBST(root.right));
            }
            else return false;
        }
        else return false;
        
        
        
    }
}

三刷。

通过in-order traversal，最后的结果是sorted的就肯定没问题，比较直白，就不说怎么做了。

这样需要一个Stack用于traversal which is O(n)

另一种方式不容易想到，代表的一种思维很关键。

Binary Search Tree是排序好的，对于一个ROOT来说，他的值要大于左边的最大值，小于右边的最小值，这就等于规定了一个区间，我们可以通过这个来判断每个ROOT是否符合规定。

~~当然bottom-up要比top-down快的多。~~

回头看发现这里说错了，不是bottom-up，这个代码的本质还是in-order traversal，记录当前上一个值，下一个值要比上一个值大，因为in-order traversal是sorted..as I mentioned above..

public class Solution {
    
    TreeNode tempMin = null;
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (isValidBST(root.left)) {
            if (tempMin == null || root.val > tempMin.val) {
                tempMin = root;
                return isValidBST(root.right);
            }
        }
        return false;
    }
}

代码里面

tempMax = root;

这一行其实是在记录previous value which should be less than next one.

一开始说的bottom-up，用post-order做应该是这样的。

public class Solution {
    
    public boolean isValidBST(TreeNode root) {

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

缺点是不能提前停止。有点太为了体现POST-ORDER的顺序，其实可以先比较，再深入，这样有问题直接停止了。

后来想了一下，这个题bottom-up不一定比top-down好。。。

另外。。最大最小值不能用Integer自带的2个，因为test case里面有。。。