# 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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/2.binary-tree/95.validate-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.