42.将有序数组转换为二叉搜索树

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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

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

【思路】

• 代码的构建逻辑是前序遍历（中→左→右）：先创建根节点，再递归构建左右子树；
• 要求平衡，选用二叉搜索树BST
• 算法的核心依据是 BST 的中序特性：有序数组是目标 BST 的中序遍历结果，因此选中间元素作为根能保证树的平衡；

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

    public TreeNode helper(int[]nums, int left, int right){
        if(left>right) return null;

        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid-1);
        root.right = helper(nums, mid+1, right);
        return root;
    }
}