Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree.

Solution: it is often easy to make mistakes in this problem. You should not only compare the value of a node with its left and right. The key point is to make sure that ALL Nodes in the left subtree must be smaller than the current node, and ALL Nodes in the left subtree should be greater than the current node. Therefore, we use a (min, max) interval to check the valid range of nodes in the left subtree and right subtree respectively.

Java语言: ValidateBST

01 public boolean isValidBST(TreeNode root) {
02     return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
03 }
04 
05 public boolean isValidBSTHelper(TreeNode root, int min, int max)
06 {
07     if(root==null)  return true;
08     if(root.val<=min || root.val>=max)
09         return false;
10     return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
11 }