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.

1.方法一

（1）思路

二叉树的中序遍历可以得到一个有序的序列。所以可以先进行中序遍历，再遍历一遍判断是否存在逆序，如果存在，证明不是一个二叉树。

（2）代码实现

class Solution {
    public boolean isValidBST(TreeNode root) {
     List<Integer> res = new ArrayList<>();//存储中序遍历序列
     TreeNode curr = root;
     Stack<TreeNode> s = new Stack<>();
     while(curr!=null || !s.isEmpty()){
         while(curr!=null){
             s.push(curr);
             curr = curr.left;
         }
         curr = s.pop();
         res.add(curr.val);
         curr = curr.right;
     }
     for(int i = 1;i<res.size();i++){
         if(res.get(i-1)>=res.get(i)){
             return false;
         }
     }
    return true;
    }
}

（3）时间、空间复杂度

①时间复杂度：while循环中每个节点都进行一次遍历左右子树，遍历二叉树时间复杂度，是O(logN)，for循环是O(N)，所以总体是O(N)
②空间复杂度：O(N)

2.方法二

（1）思路

二叉树的特性是左子树<根节点<右子树。可以通过递归进行判断是否符合max(左子树)<根节点<min(右子树)。

（2）代码实现

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(root.left!=null && root.val<=max(root.left)){
            return false;
        }
        if(root.right!=null && root.val>=min(root.right)){
            return false;
        }
        boolean left = isValidBST(root.left);
        boolean right = isValidBST(root.right);
        return (left && right);
     }
    
    public int min(TreeNode node){
        while(node.left!=null){
            node = node.left;
        }
        return node.val;
    }
    
    public int max(TreeNode node){
        while(node.right!=null){
            node = node.right;
        }
        return node.val;
    }
}

（3）时间、空间复杂度

①时间复杂度：每个节点都需要遍历一遍左右子树求最大最小值，遍历的时间复杂度与其所在高度有关，也就是O(logN)。
②空间复杂度：只用了有限几个变量，所以是O(1)