108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
思路：
因为是有序数组，使用分治的思路，寻找mid点，然后左右子树的建立使用分治，这里提供左闭右闭的思路。 如果这里使用二叉平衡树来做，左右旋转的代码量都比这里的大了，而且与题目的提供数据(有序)不太贴切，所以可以实现，但是复杂度一定会更高，在合适的场景使用合适的算法才是最好的选择，当然闲着没事做当然是可以用二叉平衡树来做，当作复习算法也可。
实现代码
class Solution {
public:
TreeNode
* makeTree(vector
<int>& nums
, int l
, int r
){
if(l
> r
) return NULL;
TreeNode
* p
;
if(l
== r
) return new TreeNode(nums
[l
]);
int mid
= (l
+ r
) >> 1;
p
= new TreeNode(nums
[mid
]);
p
->left
= makeTree(nums
, l
, mid
- 1);
p
->right
= makeTree(nums
, mid
+ 1, r
);
return p
;
}
TreeNode
* sortedArrayToBST(vector
<int>& nums
) {
return makeTree(nums
, 0, nums
.size() - 1);
}
};
