当前位置:网站首页>LeetCode 0108.将有序数组转换为二叉搜索树 - 数组中值为根,中值左右分别为左右子树
LeetCode 0108.将有序数组转换为二叉搜索树 - 数组中值为根,中值左右分别为左右子树
2022-07-05 05:45:00 【Tisfy】
【LetMeFly】108.将有序数组转换为二叉搜索树 - 数组中值为根,中值左右分别为左右子树
力扣题目链接:https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
给你一个整数数组 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
按 严格递增 顺序排列
其实我觉得这题难度设置为中等也不错
方法一:数组中值为根,中值左右分别为左右子树
顾名思义,要想让这棵树为高度平衡的二叉搜索树,我们只需要把数组的中值作为根即可。
因为把数组的中值作为根,即可达到左边右边的元素数量相等(或相差一个)的效果。
同时,题目给定的是一颗已经排序过的数组,因此数组中值左边的元素全部小于中值元素,右边全部大于。
因此把中值左边全部作为左子树,右边全部作为右子树即可。
这就变成了子问题:左右子树的构建。因此递归即可。
终止条件:要构建的数组为空。
- 时间复杂度 O ( n ) O(n) O(n),其中 n n n是数组中元素的个数。
- 空间复杂度 O ( log n ) O(\log n) O(logn),取决于递归栈的深度。
AC代码
C++
class Solution {
private:
TreeNode* build(vector<int>& nums, int l, int r) {
if (l >= r)
return nullptr;
int mid = (l + r) >> 1;
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums, l, mid);
root->right = build(nums, mid + 1, r);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size());
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/125610878
边栏推荐
- CCPC Weihai 2021m eight hundred and ten thousand nine hundred and seventy-five
- 卷积神经网络——卷积层
- Hang wait lock vs spin lock (where both are used)
- 【Jailhouse 文章】Look Mum, no VM Exits
- The sum of the unique elements of the daily question
- Codeforces round 712 (Div. 2) d. 3-coloring (construction)
- 2022 极术通讯-Arm 虚拟硬件加速物联网软件开发
- 数仓项目的集群脚本
- 智慧工地“水电能耗在线监测系统”
- Sword finger offer 58 - ii Rotate string left
猜你喜欢
lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
Fried chicken nuggets and fifa22
Sword finger offer 06 Print linked list from beginning to end
Web APIs DOM node
Using HashMap to realize simple cache
Pointnet++ learning
[practical skills] technical management of managers with non-technical background
智慧工地“水电能耗在线监测系统”
【云原生】微服务之Feign自定义配置的记录
Brief introduction to tcp/ip protocol stack
随机推荐
After setting up the database and website When you open the app for testing, it shows that the server is being maintained
Sword finger offer 58 - ii Rotate string left
Typical use cases for knapsacks, queues, and stacks
Introduction and experience of wazuh open source host security solution
26、 File system API (device sharing between applications; directory and file API)
[cloud native] record of feign custom configuration of microservices
Solution to the palindrome string (Luogu p5041 haoi2009)
剑指 Offer 35.复杂链表的复制
R语言【数据集的导入导出】
Cluster script of data warehouse project
2022年贵州省职业院校技能大赛中职组网络安全赛项规程
Codeforces Round #715 (Div. 2) D. Binary Literature
Implement an iterative stack
CF1634 F. Fibonacci Additions
Convolution neural network -- convolution layer
API related to TCP connection
Haut OJ 1401: praise energy
shared_ Repeated release heap object of PTR hidden danger
Sword finger offer 09 Implementing queues with two stacks
[practical skills] how to do a good job in technical training?