二分查找

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {

        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    /**
     * 每次将数组的中间元素作为根节点，这样得到的二分搜索树就是高度平衡的
     */
    public TreeNode sortedArrayToBST(int[] nums, int left, int right){

        if (left > right){
            return null;
        }

        int mid = left + (right - left) / 2;
        
        TreeNode root = new TreeNode(nums[mid]);

        /**
         * 根节点的左右递归的将数组一分为二
         */
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);

        return root;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(logn)
 */

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/