/**

  * Definition for binary tree

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public TreeNode sortedArrayToBST(int[] num) {

         if (num.length==0)

             return null;

         int end = num.length-1;

         TreeNode root = sortedArrayToBSTRecur(num,0,end);

         return root;

     }

     public TreeNode sortedArrayToBSTRecur(int[] num, int head, int end){

         if (head==end){

             TreeNode root = new TreeNode(num[head]);

             return root;

         }

         if (head+1==end){

             TreeNode root = new TreeNode(num[end]);

             TreeNode child = new TreeNode(num[head]);

             root.left = child;

             return root;

         }

         //Calculate the median index.

         int len = end-head;

         int mid = head + len/2 + len%2;

         TreeNode root = new TreeNode(num[mid]);

         TreeNode leftChild = sortedArrayToBSTRecur(num,head,mid-1);

         TreeNode rightChild = sortedArrayToBSTRecur(num,mid+1,end);

         root.left = leftChild;

         root.right = rightChild;

         return root;

     }

 }