题目描述

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

题目分析

二叉搜索树是 左子树 <= 根节点 <= 右子树，且左右子树也都是二叉搜索树。二叉搜索树本质是把数组的二分查找写成二叉树的形式。
数组是有序的，直接找到中点作为根节点，然后递归把左子数组变成左子树，右子数组变成右子树。

Java

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

private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
    if (start > end) {
        return null;
    }
    int mid = (start + end) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid - 1);
    root.right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

Kotlin

fun sortedArrayToBST(nums: IntArray, start: Int = 0, end: Int = nums.size - 1): TreeNode? {
    if (start > end) {
        return null
    }
    val mid = (start + end) / 2
    val root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums, start, mid - 1)
    root.right = sortedArrayToBST(nums, mid + 1, end)
    return root
}