排序数组转换为二叉查找树

已知一个排序的数组，将该数组转换为一个高度平衡的二叉查找树。
平衡的定义： 二叉查找树中，任意节点的两颗子树高度差不超过1.
LeetCode 108

思考

平衡二叉查找树：任意节点的两颗子树高度差不超过1的二叉查找树。能否将数组转换为平衡为平衡二叉排序树，关键是确认数组元素按何种顺序插入至二叉查找树

分析

将数组[1,2,3,4,5,6,7,8,9]中的元素，组成平衡二叉查找树，需要以元素5为根结点，将1、2、3、4与6、7、8、9分为两个部分。
将[1、2、3、4]中的元素，组成平衡二叉查找树，需要以元素2或3为根结点。将1与3、4（或1、2、4）分为两部分；将[6、7、8、9]中的元素，组成平衡二叉查找树，需要以元素7或8为根节点。将6与8、9(或6、7与9)分为两部分。
结论：每次选取数组的中间元素插入二叉查找树，完成选择后将数组划分为左右两个数组，再递归的处理这两个数组，继续选择数组的中间元素进行处理。

算法设计

设置递归函数，preorder_insert(const std::vector<int> &nums, std::vector<TreeNode *> &node_vec)
该函数的作用是将nums数组进行划分，begin与end代表正在划分的区间右端点，每次寻找区间的中间数据生成二叉树节点，保存在node_vec中：
当划分区间左端点大于右端点时，return
计算中间点：mid = (begin + end)/2;
构建二叉树节点，节点值为nums[mid],保存至node_vec；
递归解决中间点mid的左右两边数组数据。

void preorder_insert(const std::vevotr<int> &nums, std::vector<TreeNode *> &node_vec, int begin , int end){
    if(begin > end){
        return ;
    }
    int mid = (begin + end) / 2;
    node_vec.push_back(new TreeNode(nums[mid]));
    preorder_insert(nums,node_vec,begin,mid-1);
    preorder_insert(nums,node_vec,mid+1,end);
}
class Solution{
public:
    TreeNode * sortedArrayToBST(std:;vector<int> & nums){
         if(nums.size() == 0){
              return NULL;
          }
          std::vector<TreeNode *> node_vec;
          preorder_insert(nums, node_vec,0,nums.size()-1);
          for(int i =1; i < node_vec.size(); i++){
              BST_insert(node_vec[0],node_vec[i])
          }
          return node_vec[0]
    }
};