树--108. 将有序数组转换为二叉搜索树/medium 理解度B

1、题目

给你一个整数数组 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,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

2、题目分析

有序数组和高度平衡二叉搜索树的换算关系：
二分偏左位置的数字作为根节点。左边的数据递归作为左子树，右边的数据递归作为右子树。

3、复杂度最优解代码示例

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

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

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        // 边界条件：如果起始索引大于结束索引，则返回null
        if (start > end) return null;

        // 找到当前子数组的中间元素作为根节点
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // 递归构建左子树和右子树
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);

        return root;
    }
}

4、适用场景

将有序数组转换为二叉搜索树（BST）的操作在多个场景中都有其应用，以下是一些具体的适用场景：

1. 算法教学与学习：这个操作常用于教授递归和二叉树的基本概念，帮助学生理解二叉搜索树的性质和构建方法。
2. 数据结构转换：在某些情况下，需要将有序数组转换为二叉搜索树，以便利用二叉搜索树的特性进行高效的查找、插入和删除操作。
3. 平衡性检查：通过将有序数组转换为二叉搜索树，可以检查树的平衡性，这对于保持数据的有序性和提高搜索效率至关重要。
4. 数据库索引：在数据库系统中，二叉搜索树常用于构建索引结构，将有序数组转换为二叉搜索树有助于快速定位和检索数据。
5. 文件系统管理：在文件系统中，二叉搜索树可以用于管理和优化文件的存储结构，将有序数组转换为二叉搜索树有助于提高文件的查找和访问速度。
6. 游戏开发：在游戏中，可能需要根据一定的规则对对象进行排序和检索，将有序数组转换为二叉搜索树可以提供高效的数据访问方式。
7. 机器学习：在机器学习领域，二叉搜索树可以用于构建决策模型，将有序数组转换为二叉搜索树有助于快速评估和选择最佳的特征和参数。
8. 图的遍历：在图论中，二叉搜索树可以用于表示图的层次结构，将有序数组转换为二叉搜索树有助于分析图的性质和进行图的遍历。