leetcode算法108.将有序数组转换为二叉搜索树
2023-09-11 14:22:53 时间
👏👏👏
哈喽!大家好,我是【学无止境小奇】,一位热爱分享各种技术的博主!😍😍😍
⭐【学无止境小奇】的创作宗旨:每一条命令都亲自执行过,每一行代码都实际运行过,每一种方法都真实实践过,每一篇文章都良心制作过。✊✊✊
⭐【学无止境小奇】的博客中所有涉及命令、代码的地方,除了提供图片供大家参考,另外会在图片下方提供一份纯文本格式的命令或者代码方便大家粘贴复制直接执行命令或者运行代码。🤝🤝🤝
⭐如果你对技术有着浓厚的兴趣,欢迎关注【学无止境小奇】,欢迎大家和我一起交流。😘😘😘
❤️❤️❤️感谢各位朋友接下来的阅读❤️❤️❤️
一、leetcode算法
1、将有序数组转换为二叉搜索树
1.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,3] 和 [3,1] 都是高度平衡二叉搜索树。
1.2、思路
思路一:此题我们可以使用递归的方式来解决问题,首先遵循以下几个条件。
1.跟节点的左子树肯定小于跟节点的右子树
2.由于数组是有序的,我们可以取数组中间的数作为根节点。
1.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;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
复杂度分析
时间复杂度:O(n),其中 n 是数组的长度。每个数字只访问一次。
空间复杂度:O(logn),其中 n 是数组的长度。空间复杂度不考虑返回值,因此空间复杂度主要取决于递归栈的深度,递归栈的深度是 O(logn)。
相关文章
- Leetcode: Nth Digit
- Leetcode: Subsets II
- LeetCode高频题:戈壁滩种树,一排n棵树,至少有k棵树存活时,最终形成的风景线有多少不同的情况
- LeetCode高频题36. 有效的数独
- LeetCode高频题8:字符串转换整数 (atoi)
- 【Java数据结构与算法】LeetCode 0206. 反转链表的三种Java实现方法
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 112、【树与二叉树】leetcode ——108. 将有序数组转换为二叉搜索树:二分查找树(C++版本)
- 【LeetCode】94. Binary Tree Inorder Traversal (3 solutions)
- 【LeetCode】141. Linked List Cycle (2 solutions)
- [LeetCode] 1331. Rank Transform of an Array 数组序号转换
- [LeetCode] 1017. Convert to Base -2 负二进制转换
- [LeetCode] Exclusive Time of Functions 函数的独家时间
- [LeetCode] 60. Permutation Sequence 序列排序
- [LeetCode] Text Justification 文本左右对齐
- LeetCode将有序数组转换为二叉搜索树
- leetcode 617. Merge Two Binary Trees 合并二叉树(简单)