給你一棵二叉搜索樹，請你返回一棵 平衡后 的二叉搜索樹，新生成的樹應該與原來的樹有著相同的節(jié)點值。
如果一棵二叉搜索樹中，每個節(jié)點的兩棵子樹高度差不超過 1 ，我們就稱這棵二叉搜索樹是 平衡的 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/balance-a-binary-search-tree
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

image.png

實現(xiàn)思路：有序數(shù)組從中間開始，中間位置為根節(jié)點，左右分別為左右子樹，依次遞歸構造

代碼實現(xiàn)：

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

    public static TreeNode createBST(int[] nums, int low, int high) {
        if (low > high) return null;
        int mid = (low + high) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = createBST(nums, low, mid - 1);
        node.right = createBST(nums, mid + 1, high);
        return node;
    }