[数据结构与算法]树-----2.判断是否是二叉搜索树

第19日：验证二叉搜索树

题目链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn08xg/

题目：

给你一个二叉树的根节点root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104]内
-231 <= Node.val <= 231 - 1
相关标签 树、深度优先搜索、二叉搜索树、二叉树

解题：

1. 使用中序遍历递归

   大致思路：

   二叉搜索树需要注意的是：结点的左子树的所有结点的值比自己都要小，右子树的所有结点的值比自己都要大

   二叉搜索树的一个特点是，中序遍历的值，是从小到大有顺序的。如下图

   

   他的中序遍历结果是：

   所以我们使用中序遍历，保存它的上一个结点是谁，再跟目前结点作比对，思路就很清晰了。

   详细代码如下：

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode() {}
    *     TreeNode(int val) { this.val = val; }
    *     TreeNode(int val, TreeNode left, TreeNode right) {
    *         this.val = val;
    *         this.left = left;
    *         this.right = right;
    *     }
    * }
    */
   class Solution {
       TreeNode prev=null;
       public boolean isValidBST(TreeNode root) {
           if (root==null) return true;//如果当前结点为空，返回
           
           //如果上一次返回false（不是二叉搜索树）则结束
           if (!isValidBST(root.left)) return false;
           
           //判断中序遍历的上一个结点是否小于本身结点
           if (prev!=null&&prev.val>=root.val) return false;
           prev=root;//保存此次结点
           
           //遍历当前结点的右子树
           if (!isValidBST(root.right)) return false;
           
           return true;
       }
   }