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, , (int)nums.size() - );
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) return NULL;
int mid = left + (right - left) / ;
TreeNode *cur = new TreeNode(nums[mid]);
cur->left = helper(nums, left, mid - );
cur->right = helper(nums, mid + , right);
return cur;
}
};
我们也可以不使用额外的递归函数,而是在原函数中完成递归,由于原函数的参数是一个数组,所以当把输入数组的中间数字取出来后,需要把所有两端的数组组成一个新的数组,并且分别调用递归函数,并且连到新创建的cur结点的左右子结点上面,参见代码如下:
解法二:
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) return NULL;
int mid = nums.size() / ;
TreeNode *cur = new TreeNode(nums[mid]);
vector<int> left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + , 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/
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树的更多相关文章
-
[LeetCode] Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树
Given a singly linked list where elements are sorted in ascending order, convert it to a height bala ...
-
108 Convert Sorted Array to Binary Search Tree 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树.此题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1.示例:给定有序数组: [-10,-3,0,5,9], ...
-
[LeetCode] 108. Convert Sorted Array to Binary Search Tree 把有序数组转成二叉搜索树
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Fo ...
-
Convert Sorted List to Binary Search Tree——将链表转换为平衡二叉搜索树 &;&;convert-sorted-array-to-binary-search-tree——将数列转换为bst
Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in as ...
-
LeetCode 108. Convert Sorted Array to Binary Search Tree (有序数组转化为二叉搜索树)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 题目 ...
-
Convert Sorted Array to Binary Search Tree(将一个有序数组转换成一颗二叉搜索树)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Fo ...
-
LeetCode:Convert Sorted Array to Binary Search Tree,Convert Sorted List to Binary Search Tree
LeetCode:Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in asce ...
-
LeetCode: Convert Sorted Array to Binary Search Tree 解题报告
Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending ord ...
-
108. Convert Sorted Array to Binary Search Tree 109. Convert Sorted List to Binary Search Tree -- 将有序数组或有序链表转成平衡二叉排序树
108. Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascendin ...
随机推荐
-
linux-exp 工具+小技巧
# 工具篇 # pwntools ,gdb-peda ROPgadget-tool . EDB ## pwntools获取.安装和文档帮助 ## - pwntools: github可以搜索到 htt ...
-
设置navigationBar上面的item
//创建UIBarButtonItem UIBarButtonItem * rightButton = [[UIBarButtonItem alloc]initWithBarButtonSystemI ...
-
REST API出错响应的设计(转)
REST API应用很多,一方面提供公共API的平台越来越多,比如微博.微信等:一方面移动应用盛行,为Web端.Android端.IOS端.PC端,搭建一个统一的后台,以REST API的形式提供服务 ...
-
谓词筛选表达式的扩展库PredicateLib
PredicateLib PredicateLib是谓词筛选表达式Expression<Func<T, bool>>的一个扩展库,它可以帮你创建一个复杂且灵活的Expressi ...
-
【SMTP】常见错误码
'* 邮件服务返回代码含义 '* 500 格式错误,命令不可识别(此错误也包括命令行过长) '* 501 参数格式错误 '* 502 命令不可实现 '* 503 错误的命令序列 '* 504 命令参数 ...
-
解题:USACO06DEC Milk Patterns
题面 初见SA 用了一个常见的按$height$分组的操作:二分答案,然后按$height$分组,遇到一个$height$小于$mid$的就丢进下一组并更新答案,如果最多的那组不少于$k$个说明可行 ...
-
(转)Inno Setup入门(十九)——Inno Setup类参考(5)
本文转载自:http://blog.csdn.net/yushanddddfenghailin/article/details/17251019 单选按钮 单选按钮在安装中也很常见,例如同一个程序可以 ...
-
Windows 10 KMS 手工激活
第一.安装好Win10系统,不需要安装其他激活工具.第二.是删除默认序列号,打开命令提示符(管理员),运行 slmgr.vbs -upk,可提示已卸载了序列号. slmgr /ipk W269N-WF ...
-
POJ3090:Visible Lattice Points——题解
http://poj.org/problem?id=3090 题目大意:你站在(0,0)的点上看向第一向限的点,点和点会互相阻挡,问最多看到多少点. 很容易想到,我们能看到的点,它的横纵坐标一定是互质 ...
-
Apache实现一个ip(如:127.0.0.1)和多个域名(虚拟主机)绑定
今天在学习PHP时,有这样的一个需求:一个ip(如:127.0.0.1)和多个域名(虚拟主机)绑定,以下是我的解决方案:对Apache进行相关的配置 解决方案一:通过端口来区分不同的虚拟主机 ①按照绑 ...