Implement a function to check if a binary tree is a binary search tree.

CC150-4.5.java

package POJ;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main{
 
	/**
	 * 
	 *  4.5 Implement a function to check if a binary tree is a binary search tree.
	 * 
	 * Solution:
	 * 书上第二种
	 *  
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(n)
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		TreeNode root = new TreeNode(7);
        root.left = new TreeNode(10);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(1);
        root.right.left = new TreeNode(8);
        root.right.left.left = new TreeNode(11);
		System.out.println(so.isBST(root));
	}
	public boolean isBST(TreeNode root){
		return checkBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
	}
	private boolean checkBST(TreeNode root, int minValue, int maxValue) {
		// TODO Auto-generated method stub
		if(root==null)
			return true;
		return root.val>=minValue&&root.val<maxValue&&checkBST(root.left, minValue, root.val)&&checkBST(root.right, root.val, maxValue);
	}
	
}