[树，二叉搜索树，递归，平衡二叉树]
方法一：递归分治
因为数组是排序好的，将数组从中间一分为二，取中间的树为根节点，左边的数组用于构建左子树，右边的数组用于构建右子树。因为两边节点数量一致，可以保证树高度平衡。
递归处理，直到数组元素用尽为止。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length==0)return null;
TreeNode root;
root = createTree(nums,0,nums.length-1);
return root;
}
public TreeNode createTree(int[]nums,int left,int right){
int length = right -left;
if(length<0)return null;
else if(length ==0)return new TreeNode(nums[left]);
else{
int mid= (right-left)/2+left;
TreeNode root = new TreeNode(nums[mid]);
if(mid-left>=1) {
TreeNode leftTreeNode = createTree(nums,left,mid-1);
if(leftTreeNode!=null) {
root.left=leftTreeNode;
}
}
if(right-mid>=1) {
TreeNode rightTreeNode = createTree(nums,mid+1,right);
if(null!=rightTreeNode)
root.right = rightTreeNode;
}
return root;
}
}
}
