版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。

样例
给出数组 [1,2,3,4,5,6,7], 返回

     4
   /   \
  2     6
 / \    / \
1   3  5   7

思路：递归

/**
 * 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;
        }
        return create(A, 0, A.length - 1);
    }

    public TreeNode create(int[] A, int left, int right) {
        if(left == right){//处理[-1,1]的情况
            return new TreeNode(A[left]);
        }if (left < right) {
            int mid = (left + right) >> 1;
            TreeNode node = new TreeNode(A[mid]);
            node.left = create(A, left, mid - 1);
            node.right = create(A, mid + 1, right);
            return node;
        } else if (left == right) {//处理[-1,1]的情况
            return new TreeNode(A[left]);
        }
        return null;
    }
}