108. Convert Sorted Array to Binary Search Tree

由一个已经排序的数组构造二叉树，很容易就可以想到递归二分搜索，只是多了一个TreeNode的返回值。思路是每次取中间，再构造左右两边。

public TreeNode sortedArrayToBST(int[] nums) {
    return dfs(nums, 0, nums.length - 1);
}

public TreeNode dfs(int[] nums, int l, int r) {
    if (l > r) return null;
    int mid = (l + r) >>> 1;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = dfs(nums, l, mid - 1);
    root.right = dfs(nums, mid + 1, r);
    return root;
}

第二种边界姿势，同二分法。但是这两种方法构造出的二叉树可能是不一样的，sorted数组只是代表了中序遍历，不能确定唯一的树。

public TreeNode sortedArrayToBST(int[] nums) {
    return dfs(nums, 0, nums.length);
}

public TreeNode dfs(int[] nums, int l, int r) {
    if (l >= r) return null;
    int mid = (l + r) >>> 1;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = dfs(nums, l, mid);
    root.right = dfs(nums, mid + 1, r);
    return root;
}