题目：
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.
题解：
题目非常善良的给了binary search tree的定义。
这道题就是判断当前树是不是BST，所以递归求解就好。
第一种方法是中序遍历法。
因为如果是BST的话，中序遍历数一定是单调递增的，如果违反了这个规律，就返回false。
代码如下：
1 public boolean isValidBST(TreeNode root) {
2 ArrayList<Integer> pre = new ArrayList<Integer>();
3 pre.add(null);
4 return helper(root, pre);
5 }
6 private boolean helper(TreeNode root, ArrayList<Integer> pre)
7 {
8 if(root == null)
9 return true;
boolean left = helper(root.left,pre);
if(pre.get(pre.size()-1)!=null && root.val<=pre.get(pre.size()-1))
return false;
pre.add(root.val);
boolean right = helper(root.right,pre);
return left && right;
}
第二种方法是直接按照定义递归求解。
“根据题目中的定义来实现，其实就是对于每个结点保存左右界，也就是保证结点满足它的左子树的每个结点比当前结点值小，右子树的每个结点比当前结
点值大。对于根节点不用定位界，所以是无穷小到无穷大，接下来当我们往左边走时，上界就变成当前结点的值，下界不变，而往右边走时，下界则变成当前结点
值，上界不变。如果在递归中遇到结点值超越了自己的上下界，则返回false，否则返回左右子树的结果。”
代码如下：
1 public boolean isValidBST(TreeNode root) {
2 return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
3 }
4
5 public boolean isBST(TreeNode node, int low, int high){
6 if(node == null)
7 return true;
8
9 if(low < node.val && node.val < high)
return isBST(node.left, low, node.val) && isBST(node.right, node.val, high);
else
return false;
}
Reference：http://blog.csdn.net/linhuanmars/article/details/23810735