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.

1.思路

平衡二叉树满足左子节点<根节点<右子节点，并且左右子树高度相差不超过1。而对平衡二叉树进行中序遍历可以得到一个顺序的结果。

那么在一个有序的数组中，中位数就是二叉树的根节点，中位数左右两边递归下去就能分别找到子树的根节点了。

2.代码实现

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


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