L108. Convert Sorted Array to Binary Search Tree

Problem:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution:

• create a new node cur as the root which is the mid value;

public TreeNode convertToTree(int[] array){
    if(array == null || array.length == 0) return null;
    return convert(0, array.length - 1, array);
}
private TreeNode convert(int start, int end, int[] array){
    if(start > end) return null;
    int mid = start + (end - start)/2;
    TreeNode cur = new TreeNode(array[mid]);
    cur.left = (start, mid-1, array);
    cur.right = (mid+1, end, array);
    return cur
}