将有序数组转换为二叉搜索树（平衡）

0x01.问题

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

C++结构体：
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 函数形式：    TreeNode* sortedArrayToBST(vector<int>& nums)     
 

0x02.简要分析

问题大致是将一个有序的数组转换成平衡的二叉搜索树。

我们不要看到平衡就开始想着如何去转话平衡了，因为转换平衡确实工作量有点大，我们可以发现，题目还有一个有利条件，就是数组是有序的，有序有什么用呢？

二叉搜索树的中序遍历得到的序列不就是一个有序序列嘛，我们可以将这个中序序列转化为一个平衡的二叉树。该如何转化呢？

我们知道，中序遍历序列的中点一定是二叉树的根，对于奇数个来说，就是中间那个，对于偶数个来说，中间两个都可以作为根，我们可以先找到这个根，然后把这个序列分为左右两个部分，左边是一个有序序列，那么左边的中点就是根的左子树，右边的中点就是根的右子树，这两个子树同样也可以看作下面那些子树的根，所以，我们只要不断地取数列的中点，不断的递归调用，就能完成这个创建平衡搜索二叉树的过程，为什么这样创建的一定是平衡的呢？

因为左边的个数和右边的个数相差绝对不会超过1，如果是偶数个，选择中点后，左右两边相差1，如果是奇数个，选择中点后，左右个是相等的。

注意：

• 由中序遍历得到的二叉树是不唯一的，所以在选择中点的时候，就可以有多种选择。
• 这个过程其实是按前序遍历创建的是，但是使用的序列是中序的。
• 这其实也算是一个二分的过程，在这里终止条件是left>right。

0x03.将有序数组转化为平衡的二叉搜索树

class Solution {
public:
    TreeNode* helper(int left,int right,vector<int>& nums){
        if(left>right) return NULL;
        int mid=(left+right)/2;
        TreeNode*root=new TreeNode(nums[mid]);
        root->left=helper(left,mid-1,nums);
        root->right=helper(mid+1,right,nums);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(0,nums.size()-1,nums);
    }
};

ATFWUS --Writing By 2020–03–26