027.将有序数组转换为二叉搜索树
题目链接：
108. 将有序数组转换为二叉搜索树
大概思路：
题目要求：
给一个升序数组，把它转化为高度平衡二叉搜索树。
高度平衡二叉树：
一个节点的左右子树高度差一定不超过1。
思路：
取数组中间作为分割点，然后划分左右区间，然后再取左右区间的中间节点作为分割点，然后继续划分下去，不断循环，直至二叉搜索树构造完成
数组构造二叉搜索树，用中间节点不断划分的话，那必然是平衡树，脑补下过程，最大差最多一颗树
递归三部曲：
1.确定递归函数参数和返回类型：
划分区间是闭区间[left, right],参数为数组，左右区间的数值
TreeNode* traversal(vector<int>& nums, int left, int right) {2.明确终止条件：
当函数构造到函数最后一个节点，此时没有再按mid划分区间的话，+-1会让这个条件达成
if (left > right) return nullptr;3.确定递归单层逻辑：
取数组中间的值，然后构造新节点返回，同时以这个数值中间值为分割点，划分左右区间,最后返回该节点
//可以避免两个节点值加起来突破内存上限的同时,
//也可以让数组长度为偶数的时候,取中间靠左的数组作为中间节点
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;4.总代码：
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};