【C++刷题】力扣-#108-将有序数组转换为二叉搜索树

题目描述

给定一个升序排列的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树（BST）。高度平衡的二叉搜索树定义为：一个二叉搜索树，其中左右两个子树的高度差不超过 1。

示例

示例 1

输入: nums = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5,null,9]
解释: 如上图所示，高度平衡的二叉搜索树有两个可能的树结构。返回任何一个都是可以的。

示例 2

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

题解

这个问题可以通过递归的方式来解决。基本思路是找到数组的中间元素作为根节点，然后对左右两边的子数组递归执行相同的操作。

1. 找到中间元素：计算数组的中间索引 mid。
2. 创建根节点：将 nums[mid] 作为根节点。
3. 递归构建左右子树：对 mid 左边的子数组和 mid 右边的子数组递归执行相同的操作，分别构建左子树和右子树。
4. 返回根节点：递归结束后，返回根节点。

代码实现

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);
}

TreeNode* sortedArrayToBSTHelper(vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;
    
    int mid = start + (end - start) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBSTHelper(nums, start, mid - 1);
    root->right = sortedArrayToBSTHelper(nums, mid + 1, end);
    
    return root;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素都被访问一次。
● 空间复杂度：O(log n)，这是因为递归调用的深度是树的高度，对于平衡二叉树，高度大约是 log(n)。
这个算法的优势在于它利用了数组的有序性，通过递归快速构建了二叉搜索树。