### 题目

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. Example 1:

    2
/ \
1   3


Binary tree [2,1,3], return true. Example 2:

    1
/ \
2   3


Binary tree [1,2,3], return false.

### 分治法递归

    1
/ \
2   3


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBSTRecur(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
public boolean isValidBSTRecur(TreeNode root, int min, int max) { // range inclusive
if (root == null) { return true; }
int value = root.val;
if (root.left != null) {
int left = root.left.val;
if (left < min || left >= value) { return false; }
}
if (root.right != null) {
int right = root.right.val;
if (right > max || right <= value) { return false; }
}
return isValidBSTRecur(root.left,min,value-1) && isValidBSTRecur(root.right,value+1,max);
}
}


### 把递归的终结条件往下推一层

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValideBSTRecur(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValideBSTRecur(TreeNode root, long min, long max) { // range inclusive
if (root == null) { return true; }
if (root.val < min || root.val > max) { return false; }
return isValideBSTRecur(root.left,min,(long)root.val-1) && isValideBSTRecur(root.right,(long)root.val+1,max);
}
}


### 用迭代版的inorder traversal方法也可以

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) { return true; }
TreeNode cur = root;
long pre = Long.MIN_VALUE;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.offerFirst(cur);
cur = cur.left;
}
cur = stack.pollFirst();
if (cur.val <= pre) { return false; }
pre = cur.val;
cur = cur.right;
}
return true;
}
}