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

力扣传送门(opens new window)

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

示例 1：

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

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解题思路：

具体的解题思路如下：

1. 首先判断输入的数组 nums 是否为空或长度为 0。如果是，则直接返回空。
2. 定义 left 和 right 分别表示数组的左边界和右边界。初始时，left 为 0，right 为数组的长度。
3. 调用 createTree 方法，传入数组 nums、left 和 right，得到转换后的二叉搜索树。
4. 在 createTree 方法中，首先判断左边界 left 是否大于等于右边界 right。如果是，表示当前子数组为空，返回空节点。
5. 计算中间位置 mid，可以通过 (left + right) / 2 得到。将 nums[mid] 的值作为根节点的值，创建一个新的节点。
6. 递归调用 createTree 方法，传入数组 nums、left 和 mid，得到左子树。将左子树连接到根节点的左节点上。
7. 递归调用 createTree 方法，传入数组 nums、mid + 1 和 right，得到右子树。将右子树连接到根节点的右节点上。
8. 返回根节点。

通过不断地二分数组并将中间元素作为根节点，然后递归构建左右子树，最终可以得到一个高度平衡的二叉搜索树。由于输入的数组是有序的，所以转换后的二叉搜索树的中序遍历结果将与原数组相同。

代码实现：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int left = 0;
        int right = nums.length;
        return createTree(nums, left, right);
    }

    public TreeNode createTree(int[] nums, int left, int right) {
        // 左边界大于等于右边界，表示当前子数组为空，返回空节点
        if (left >= right) {
            return null;
        }
        // 计算中间位置
        int mid = (left + right) / 2;
        // 中间元素作为根节点值，创建新节点
        TreeNode node = new TreeNode(nums[mid]);
        // 递归构建左子树，传入左边界和中间位置
        node.left = createTree(nums, left, mid);
        // 递归构建右子树，传入中间位置+1和右边界
        node.right = createTree(nums, mid + 1, right);
        // 返回根节点
        return node;
    }
}