[LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
2023-09-11 14:21:39 时间
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5
这道题是要将有序数组转为二叉搜索树,所谓二叉搜索树,是一种始终满足左<根<右的特性,如果将二叉搜索树按中序遍历的话,得到的就是一个有序数组了。那么反过来,我们可以得知,根节点应该是有序数组的中间点,从中间点分开为左右两个有序数组,在分别找出其中间点作为原中间点的左右两个子节点,这不就是是二分查找法的核心思想么。所以这道题考的就是二分查找法,代码如下:
解法一:
class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return helper(nums, 0 , (int)nums.size() - 1); } TreeNode* helper(vector<int>& nums, int left, int right) { if (left > right) return NULL; int mid = left + (right - left) / 2; TreeNode *cur = new TreeNode(nums[mid]); cur->left = helper(nums, left, mid - 1); cur->right = helper(nums, mid + 1, right); return cur; } };
我们也可以不使用额外的递归函数,而是在原函数中完成递归,由于原函数的参数是一个数组,所以当把输入数组的中间数字取出来后,需要把所有两端的数组组成一个新的数组,并且分别调用递归函数,并且连到新创建的cur结点的左右子结点上面,参见代码如下:
解法二:
class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if (nums.empty()) return NULL; int mid = nums.size() / 2; TreeNode *cur = new TreeNode(nums[mid]); vector<int> left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + 1, nums.end()); cur->left = sortedArrayToBST(left); cur->right = sortedArrayToBST(right); return cur; } };
类似题目:
Convert Sorted List to Binary Search Tree
参考资料:
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
相关文章
- Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
- Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
- Java实现 LeetCode 701 二叉搜索树中的插入操作(遍历树)
- Java实现 LeetCode 581 最短无序连续子数组(从两遍搜索找两个指针)
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 268 缺失数字
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 160 相交链表
- Java实现 LeetCode 108 将有序数组转换为二叉搜索树
- Java实现 LeetCode 96 不同的二叉搜索树
- Java实现 LeetCode 212 单词搜索 II
- 【二叉搜索树】LeetCode 96. 不同的二叉搜索树【中等】
- LeetCode(33):搜索旋转排序数组
- 每日一道 LeetCode (24):将有序数组转换为二叉搜索树
- 【二分】LeetCode 33. 搜索旋转排序数组【中等】
- LeetCode(109):有序链表转换二叉搜索树
- LeetCode(108):将有序数组转换为二叉搜索树
- LeetCode-385. 迷你语法分析器【深度优先搜索,栈】
- 【leetcode 33】搜索旋转排序数组(第二遍)
- Leetcode 81. 搜索旋转排序数组 II
- Leetcode 74. 搜索二维矩阵
- [LeetCode] 33. 搜索旋转排序数组 ☆☆☆(二分查找)
- 力扣LeetCode,区域和检索 - 数组可修改
- 【Leetcode刷题Python】450. 删除二叉搜索树中的节点
- LeetCode 653. 两数之和 IV - 输入二叉搜索树
- leetcode 搜索旋转排序数组