Recursive Solution - Convert Sorted Array to Binary Search Tree

The idea is to find the middle node as the current root, and root.left = the middle of the first half, and root.right = the middle of the second half. Watch the index… begin, middle-1/middle+1, end…middle...


/**
 * 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 == null || num.length == 0){
            return null;
        }
        if(num.length == 1){
            return new TreeNode(num[0]);
        }
     
        return sortedArrayToBSTOps(num, 0, num.length - 1);
    }
 
    private TreeNode sortedArrayToBSTOps(int[] num, int begin, int end){
        if(begin > end){
            return null;
        }
        if(begin == end){
            return new TreeNode(num[begin]);
        }
        int mid = (begin + end) / 2;
        TreeNode curN = new TreeNode(num[mid]);
        curN.left = sortedArrayToBSTOps(num, begin, mid - 1);
        curN.right = sortedArrayToBSTOps(num, mid + 1, end);
        return curN;
    }
}