[LeetCode]Ar108 有序数组转换为二叉搜索树

🚩传送门：https://leetcode-cn.com/problems/merge-sorted-array/

题目

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

示例 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,3] 和 [3,1] 都是高度平衡二叉搜索树。

📖 文字题解

二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

给定二叉搜索树的中序遍历，是否可以唯一地确定二叉搜索树？答案是否定的。

任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。

如果增加一个限制条件，即要求二叉搜索树的高度平衡，是否可以唯一地确定二叉搜索树？答案是否定的。

直观地看，我们可以选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡。

1. 如果数组长度是奇数，则根节点的选择是唯一的
2. 如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。

解题思路：

🚩重点：确定平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树，因此可以通过 递归 的方式创建平衡二叉搜索树。

当然，这只是我们直观的想法，为什么这么建树一定能保证是「平衡」的呢？

这里可以参考「1382. 将二叉搜索树变平衡」

递归的基准情形是平衡二叉搜索树不包含任何数字，此时平衡二叉搜索树为空。

三种方式

1. 方式一总是选择中间位置左边的数字作为根节点
2. 方式二总是选择中间位置右边的数字作为根节点
3. 方式三是方式一和方法二的结合，选择任意一个中间位置数字作为根节点。

复杂度分析

时间复杂度：，其中 是数组的长度。

每个数字只访问一次。

空间复杂度：，其中 是数组的长度。

空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 。

代码

选择中间位置左边的数字作为根节点，则根节点的下标为 ，此处除法为整数除法。

选择中间位置右边的数字作为根节点，则根节点的下标为 ，此处除法为整数除法。

选择任意一个中间位置数字作为根节点，则根节点的下标为上面两种中的任意一个，此处的除法为整数除法。

官方代码：

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;
        // 总是选择中间位置右边的数字作为根节点
        int mid = (left + right + 1) / 2;
        // 选择任意一个中间位置数字作为根节点
        int mid = (left + right + rand.nextInt(2)) / 2;
        //========================
        //       任选一种mid方式
        //========================
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}