Convert Sorted Array to Binary Search Tree With Minimal Height

• LintCode: No.177-Convert Sorted Array to Binary Search Tree With Minimal Height
• 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
  

• Analysis:

  Found the mid position's value as the root node.  
  Thought [left, mid - 1] and [mid + 1, right] as children recursively.
  

• Java:

  • Recursive:

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

• Time Complexity:

  • O(n), n is the number of nodes