> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/2.binary-tree/95.validate-binary-search-tree.md).

# 98.Validate Binary Search Tree(M)

## 1.Description(Medium)

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

* The left subtree of a node contains only nodes with keys

  **less than**

  the node's key.
* The right subtree of a node contains only nodes with keys

  **greater than**

  the node's key.
* Both the left and right subtrees must also be binary search trees.
* A single node tree is a BST

**Example**

An example:

```
  2
 / \
1   4
   / \
  3   5
```

The above binary tree is serialized as`{2,1,4,#,#,3,5}`(in level order).

## **2.Code**

**Version 1:**

根据题目中的定义来实现，其实就是对于每个结点保存左右界，也就是保证结点满足它的左子树的每个结点比当前结点值小，\
右子树的每个结点比当前结点值大。对于根节点不用定位界，所以是无穷小到无穷大，接下来当我们往左边走时，上界就变成当前结点的值，下界不变，而往右边走时，下界则变成当前结点值，上界不变。\
如果在递归中遇到结点值超越了自己的上下界，则返回false，否则返回左右子树的结果

```
public boolean isValidBST1(TreeNode root){
         return helper(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

     }
     public boolean helper(TreeNode root,int min,int max){
         if(root==null){
             return true;
         }

        if(root.val>=max || root.val<=min){
            return false;
        }
        return helper(root.left,min,root.val)&& helper(root.right,root.val,max);
     }
```

\*放在Lintcode中跑不过是因为testcase 中就一个根结点而且根结点超过Integer.MAX\_VALUE

testcase:\[2147483647]

对于这种情况， 可以改成以下代码可以避免：

```java
boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}
```

**Version 2: I**n order traverse (use a static variable to store the previous value)

1. 对一个BST进行inorder traverse，必然会得到一个严格单调递增序列，否则则是invalid BST。
2. Inorder traverse时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

这个做法不会过只有一个元素而且这个元素比Integer.MIN\_VALUE还小的值。

testcase:\[-2147483648]

```
    public static int previous=Integer.MIN_VALUE;
    public boolean isValidBST2(TreeNode root){

        if(root==null){
            return true;
        }
        //the left tree
        if(isValidBST2(root.left)==false){
            return false;
        }

        //the current node
        if(root.val<=previous){
            return false;
        }
        previous=root.val;

        //the right tree
        if(isValidBST2(root.right)==false){
            return false;
        }

        return true;
    }
```

改进：

加一个firstNode的判断，一开始是true, 第一次运行后立刻改成false

```
    public int previous=Integer.MIN_VALUE;
    public boolean firstNode=true;

    public boolean isValidBST(TreeNode root) {

       if(root==null){
           return true;
       }
       //left tree:
       if(isValidBST(root.left)==false){
           return false;
       }

       //current node
       if(!firstNode && root.val<=previous){
           return false;
       }
       firstNode=false;
       previous=root.val;

       //right tree
       if(isValidBST(root.right)==false){
           return false;
       }

       return true;
    }
```