LeetCode每日一题： 验证二叉搜索树

先说一下我做这个题时遇到的坑把，就是我一开始的思路就是直接遍历每一个节点，然后判断其左孩子是否小于该节点，右孩子是否大于该节点，很简单的几行代码就实现了，当时还在想怎么可能这么简单，后面才发现事情没那么简单。。。。

• 如果按照上面这种方法，那么下面这颗树也应该是一颗二叉搜索树，但是由于7大于6，所以该树不是一颗二叉搜索树。介绍完坑之后，再看看正确的解法吧

  
  

中序遍历法

中序遍历该二叉树，其遍历结果一点会是升序排列，只需要比较前后两节点大小即可，至于为什么中序遍历结果会是升序排列，可以看看这篇博客：https://www.jianshu.com/p/32899bd9b69a

• 代码实现：

  class Solution {
  TreeNode pre = null; //指向前一个节点
  boolean flag = true;
  public boolean isValidBST(TreeNode root) {
   if(root == null){
     return true;
   }
  if(root.left != null){
      isValidBST(root.left);
  }
  if(pre != null){
      //比较前后两节点大小
      if(pre.val >= root.val){
          flag = false;
      }
      pre = root;
  }else{
      pre = root;
  }
   if(root.right != null){
     isValidBST(root.right);
  }
  return flag;
  }
  }
  

递归的空间复杂度似乎都不太行，看来时间复杂度最佳和空间复杂度二者只能求其一啊