给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左

  子树

  只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

方法一：中序遍历

从最左下开始，按照中序遍历的顺序，是满足从小到大的（如果是二叉搜索树）

public boolean isValidBST(TreeNode root){
    Deque<TreeNode> stack = new LinkedList<>();
    double inorder = -Double.MAX_VALUE;
    while(!stack.isEmpty() || root != null){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if(root.val <= inorder) return false;
        inorder = root.val;// 记录下这个值
        root = root.right;// 对于树[2, 1, 3]做完这个操作，再次进去内层while循环中，
        // 如果是null，会得到2,不是null进去一直向左子树深入直到为null，这里会得到3
    }
    retur true;
}

方法二：递归

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