当前位置: 首页> 汽车> 新车 > 上海建设工程检测行业协会_优购物官方网站直播_软文代理平台_我们公司在做网站推广

上海建设工程检测行业协会_优购物官方网站直播_软文代理平台_我们公司在做网站推广

时间:2025/7/11 14:58:29来源:https://blog.csdn.net/FRF65/article/details/142938564 浏览次数: 0次
上海建设工程检测行业协会_优购物官方网站直播_软文代理平台_我们公司在做网站推广

题目描述

给定一个升序排列的整数数组 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)。
这个算法的优势在于它利用了数组的有序性,通过递归快速构建了二叉搜索树。

关键字:上海建设工程检测行业协会_优购物官方网站直播_软文代理平台_我们公司在做网站推广

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: