Determine if a given binary tree is binary search tree.

Assumptions

• There are no duplicate keys in binary search tree.
• You can assume the keys stored in the binary search tree can not be Integer.MIN_VALUE or Integer.MAX_VALUE.

Corner Cases

• What if the binary tree is null? Return true in this case.

//思路：BST的话，每个节点的值要在范围内，所以可以recursively把value从上往下传

//time: 每一层call recursion function两次，所以2+4+8+... = O(n)

//space: 每一层是O(1)，所以是O（height） (height = logn if balanced, height = n if unbalanced)

  public boolean isBST(TreeNode root) {
    return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
  private boolean helper(TreeNode root, int min, int max) {
    if (root == null) {
      return true;
    }
    if (root.key < min || root.key > max) {
      return false;
    }
    return helper(root.left, min, root.key - 1) && helper(root.right, root.key + 1, max);
  }

如果有key是Integer.MIN_VALUE or Integer.MAX_VALUE，可以用Long.XXX

    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean helper(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

或者传node，而不是传值

bool isValidBST(TreeNode* root) {
    return isValidBST(root, NULL, NULL);
}

bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
    if(!root) return true;
    if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
        return false;
    return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}