98. Validate Binary Search Tree

    /*
     * 98. Validate Binary Search Tree 
     * 11.23 By Mingyang 
     * 这个题目开始用dfs的循环做时，我第一次把root的null的判断写在主函数里面，殊不知这么仅仅判断了root
     * 子分支并没有做判断。另外需要注意的是用long不用int，否则会溢出。
     * 另外一种方法就是Tree里面的中序遍历。dfs用stack实现
     * 那么dfs的方法还有一个注意的就是long的运用，开始用的int，Input:[2147483647]
     * Output:false  Expected:true
     */
    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);
    }
    public boolean isValidBST1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode p = stack.pop();
                //这里出现的p就是inorder里面不断出现的最小的数，就是最左边的数
                if (pre != null && p.val <= pre.val) {
                    return false;
                }
                pre = p;
                cur = p.right;
            }
        }
        return true;
    }