給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設(shè)一個二叉搜索樹具有如下特征：

節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:

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

輸入:
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 4 。

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

1.初始化一個最小值，用來作為最開始的前節(jié)點(diǎn)，其實就是怎么樣第一次遍歷的判斷都是對的

2.根據(jù)中序遍歷的規(guī)則，從最左子節(jié)點(diǎn)開始遍歷，訪問左子樹，一直遞歸訪問到最后一個左子樹節(jié)點(diǎn)

3.判斷是否大于前一個節(jié)點(diǎn)的值（由于一開始設(shè)置了），不是的話，就返回false

4.遞歸訪問右子樹，右子樹有左子樹就先去到最左的子節(jié)點(diǎn)開始遍歷

復(fù)雜度分析：

時間復(fù)雜度 O(N)： 遍歷了所有樹節(jié)點(diǎn)，所以時間復(fù)雜度為N。

空間復(fù)雜度 O(1)： 最差情況下，二叉樹退化為鏈表，系統(tǒng)使用 O(N) 大小的?？臻g。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    //利用中序遍歷的原理，所有遍歷的節(jié)點(diǎn)都比前一個節(jié)點(diǎn)的值大
class Solution {
    //初始化一個最小值，用來作為最開始的前節(jié)點(diǎn)，其實就是怎么樣第一次遍歷的判斷都是對的
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //如果節(jié)點(diǎn)為空，直接返回true
        if(root == null) return true;
        
        //訪問左子樹，一直遞歸訪問到最后一個左子樹節(jié)點(diǎn)
        if(!isValidBST(root.left)){
            return false;
        }
        
        //判斷是否大于前一個節(jié)點(diǎn)的值（由于一開始設(shè)置了），不是的話，就返回false
        if(pre >= root.val) return false;
        pre = root.val;
        
        //訪問右子樹
        return isValidBST(root.right);
      
    }
}