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;
    }
};