力扣108 将有序数组转换为二叉搜索树

题目：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

思路：

在刷过力扣106 从中序与后序遍历序列构造二叉树之后，应该明白构造一棵二叉树的递归流程。

本题给出的数组是升序数组，所以完全可以找到切割点作为根节点，然后递归左右区间，生成左右子树，保证单层逻辑符合right-left==1即可得到平衡树。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //1.二叉搜索树//2.平衡树
        return sortedArrayToBST(nums, 0, nums.length);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if(right<=left){
            return null; 
        }
        if (right-left==1) {
            return new TreeNode(nums[left]);
        }
        //递归处理左右区间
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,left,mid);//生成左子树
        root.right=sortedArrayToBST(nums,mid + 1,right);//生成右子树
        return root;
    }
}