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:

    1. Given the sorted array: [-10,-3,0,5,9],
    3. One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
    5.       0
    6.      / \
    7.    -3   9
    8.    /   /
    9.  -10  5

    题意

    将一个有序数组转换成左右子树高度差不超过1的平衡二叉查找树。

    思路

    递归处理，每次在待选数中选择中位数作当前子树的根，再递归生成左子树和右子树。

    代码实现

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public TreeNode sortedArrayToBST(int[] nums) {
    12.         return sortedArrayToBST(nums, 0, nums.length - 1);
    13.     }
    15.     private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
    16.         if (left > right) {
    17.             return null;
    18.         }
    20.         int mid = (left + right) / 2;
    21.         TreeNode x = new TreeNode(nums[mid]);
    23.         x.left = sortedArrayToBST(nums, left, mid - 1);
    24.         x.right = sortedArrayToBST(nums, mid + 1, right);
    26.         return x;
    27.     }
    28. }