Problem

Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.

Example

Given [1,2,3,4,5,6,7], return

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

Note

二分法找到数组的中位数，置为树的root，递归找到前半段和后半段的中位数，分别置为左右子树。直到start = mid或end = mid为止。

Solution

public class Solution {
    public TreeNode sortedArrayToBST(int[] A) {  
        return helper(0, A.length - 1, A);
    }  
    public TreeNode helper(int start, int end, int[]A) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(A[mid]);
        root.left = helper(start, mid - 1, A);
        root.right = helper(mid + 1, end, A);
        return root;
    }
}