Convert Sorted Array to Binary Search Tree With Minimal Height

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

Notice

There may exist multiple valid solutions, return any of them.

Example

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

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

Analysis:

Recursively do this:

pick middle element as root, call buildTree(lefthalf of array) for root.left, call buildTree(right half of array) for root.right

Complexity:

Time: O(N)

Space: O(N)

Code:

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

    private TreeNode buildTree(int[] A, int s, int e){
        if(s > e){
            return null;
        }

        int m = s + (e - s) / 2;
        TreeNode root = new TreeNode(A[m]);
        root.left = buildTree(A, s, m-1);
        root.right = buildTree(A, m+1, e);
        return root;
    }
}