LintCode：177. 把排序数组转换为高度最小的二叉搜索树

题目：

思路：直接采用中间值来作为二叉树的根节点；将原数组分成左右均等或者相差一个数的两个新数组；然后递归的对这两个新数组进行相同的处理，这样对于每一个根节点，其左右子树的高度相差绝对值不会超过1，也就是满足了二叉平衡树的要求了。

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param A: an integer array
     * @return: A tree node
     */
    public TreeNode sortedArrayToBST(int[] A) {
        // write your code here
        if(A==null||A.length==0) return null;
        int begin=0;int end=A.length-1;
        int mid=(begin+end)/2;
        TreeNode pRoot=new TreeNode(A[mid]);
        pRoot.left=sortedArrayToBSTCore(A,begin,mid-1);
        pRoot.right=sortedArrayToBSTCore(A,mid+1,end);
        return pRoot;
    }

    public TreeNode sortedArrayToBSTCore(int[] A,int begin,int end){
        if(begin>end){
            return null;
        }
        int mid=(begin+end)/2;
        TreeNode treeNode=new TreeNode(A[mid]);
        treeNode.left=sortedArrayToBSTCore(A,begin,mid-1);
        treeNode.right=sortedArrayToBSTCore(A,mid+1,end);
        return treeNode;
    }
}