二叉树-验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

最后参考了甜姨sweetiee的题解，pre真的是一步到位啊

1.初始化一个最小值，用来作为最开始的前节点，其实就是怎么样第一次遍历的判断都是对的

2.根据中序遍历的规则，从最左子节点开始遍历，访问左子树，一直递归访问到最后一个左子树节点

3.判断是否大于前一个节点的值（由于一开始设置了），不是的话，就返回false

4.递归访问右子树，右子树有左子树就先去到最左的子节点开始遍历

复杂度分析：

时间复杂度 O(N)： 遍历了所有树节点，所以时间复杂度为N。

空间复杂度 O(1)： 最差情况下，二叉树退化为链表，系统使用 O(N) 大小的栈空间。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    //利用中序遍历的原理，所有遍历的节点都比前一个节点的值大
class Solution {
    //初始化一个最小值，用来作为最开始的前节点，其实就是怎么样第一次遍历的判断都是对的
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //如果节点为空，直接返回true
        if(root == null) return true;
        
        //访问左子树，一直递归访问到最后一个左子树节点
        if(!isValidBST(root.left)){
            return false;
        }
        
        //判断是否大于前一个节点的值（由于一开始设置了），不是的话，就返回false
        if(pre >= root.val) return false;
        pre = root.val;
        
        //访问右子树
        return isValidBST(root.right);
      
    }
}