CC150 4.3

4_3.java

/*
4.3
Given a sorted (increasing order) array with unique integer elements, 
write an algorithm to create a binary search tree with minimal height.
*/



/*
解析:给定一个增序数组，其中包含的都是unique的整数。生成minimal height的BST。
其实也就是意味着，对于任何一个节点的左子树和右子树都尽量height balanced, 这样就可以保证minimal height.
我们知道，BST的一个特点就是对于任何一个节点为根的左子树的所有节点值都小于根节点的值，所有右子树的节点的值都大于根节点的值。且BST的
inorder遍历结果即为increasing order的。因此，我们只需要用分治+二分法策略，来不断得到子树的根即可。即原始数组的middle是整棵树的root,
左侧序列的middle即左子树的root, 右侧序列的middle即右子树的root, 这样不断递归找下去即可。
*/
// 时间复杂度: O(n)
// 空间复杂度: 最后解集即BST的空间为O(n), 递归消耗的system stack为O(logn)


package cc150Test;


class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}


public class Test {

	public static TreeNode createBST(int[] arr){
		if( arr == null || arr.length == 0 ){
			return null;
		}
		int length = arr.length;
		int start = 0, end = length - 1;
		TreeNode bstRoot = helper(arr, start, end);
		return bstRoot;
	}

	public static TreeNode helper(int[] arr, int start, int end){
		if( start > end ){
			return null;
		}
		int middle = start + ( ( end - start ) >> 1 );
		TreeNode root = new TreeNode(arr[middle]);
		root.left = helper(arr, start, middle - 1);
		root.right = helper(arr, middle + 1, end);
		return root;
	}

	public static int getMaxHeight(TreeNode root){
		if( root == null ){
			return 0;
		}
		int left = getMaxHeight(root.left);
		int right = getMaxHeight(root.right);
		return Math.max(left,right) + 1;
	}

	public static void main(String[] args) {
		int[] arr0 = new int[]{};  // min height = 0
		int[] arr1 = new int[]{1}; // min height = 1
		int[] arr2 = new int[]{1,2}; // min height = 2
		int[] arr3 = new int[]{1,2,3}; // min height = 2
		int[] arr4 = new int[]{2,3,4,5,6,7,8,9};// min height = 4
		int[] arr5 = new int[]{2,3,4,5,6,7,8}; // min height = 3

		TreeNode root0 = createBST(arr0);
		TreeNode root1 = createBST(arr1);
		TreeNode root2 = createBST(arr2);
		TreeNode root3 = createBST(arr3);
		TreeNode root4 = createBST(arr4);
		TreeNode root5 = createBST(arr5);
		System.out.println( getMaxHeight(root0) == 0 );
		System.out.println( getMaxHeight(root1) == 1 );
		System.out.println( getMaxHeight(root2) == 2 );
		System.out.println( getMaxHeight(root3) == 2 );
		System.out.println( getMaxHeight(root4) == 4 );
		System.out.println( getMaxHeight(root5) == 3 );
		
	}		
}