98. 验证二叉搜索树

题目描述：

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

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

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

示例 1:

示例 2:

思路：

思路参考：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/zhong-xu-bian-li-qing-song-na-xia-bi-xu-miao-dong-/

二叉搜索树的中序遍历是递增序列，所以只需要使用中序遍历方式遍历二叉树，判断当前结点是否大于上一个结点，如果不符合直接返回false  注意：preVal必须使用Long类型，因为担心某个结点的值刚好等于Integer.MIN_VALUE

 1 class Solution {
 2     public long preVal = Long.MIN_VALUE; // 使用Long类型是担心某个结点的值刚好等于Integer.MIN_VALUE
 3     public boolean isValidBST(TreeNode root) {
 4         if(root == null){
 5             return true;
 6         }
 7 
 8         if(!isValidBST(root.left)){ // 判断左子树是否是二叉搜索树
 9             return false;
10         }
11         if(root.val <= preVal){
12             return false;
13         }
14         preVal = root.val;
15         return isValidBST(root.right);
16     }
17 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：38.3 MB > 80.46%

复杂度分析：

时间复杂度：O(n)。n 是结点个数，使用中序遍历的方式遍历了整棵树的所有结点，所以时间复杂度为O(n)。 空间复杂度：O(n)。空间复杂度取决于栈的深度，栈的深度又取决于树的高度，所以空间复杂度最坏为树退化成链表时复杂度为O(n)。