https://leetcode.com/problems/validate-binary-search-tree/description/http://www.lintcode.com/en/problem/validate-binary-search-tree/

http://www.lintcode.com/en/problem/validate-binary-search-tree/

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).

解题：这题主要考察对二叉查找树多性质，就是验证left node值小于，right node值大于当前值。 我们在分治方法中传入2个参数，min，max用来表示当前node的值valid的范围，然后记得进入下一层之前跟新左右子节点的min，max。

public class Solution {
     public boolean isValidBST(TreeNode root) {
        return divCon(root, Long.MIN_VALUE, Long.MAX_VALUE);
     }

     public boolean divCon(TreeNode root, long min, long max) {
         if (root == null) {
             return true;
         }
         //if current node out of its range
         if (root.val <= min || root.val >= max) {
             return false;
         }
         //left child will no bigger than its parent, right child will no smaller than its parent
         return divCon(root.left, min, Math.min(max, root.val)) && divCon(root.right, Math.max(min, root.val), max);
     }
}