//平衡二叉搜索数，关键在于平衡两个字，左右数的高度差不超过1，搜索树，左节点小于 根节点 小于右节点
//先谈平衡，我们找到数组的中间节点作为数的根节点，这个方法被论证过是可行的，然后我们要构建左右子树，
//在根结点处将数组一分为二，考虑左节点，应该选取左半数组中的那个数？最大的？最小的？都不行，需要选中间的
//左节点这颗子树也要是一颗平衡二叉搜索数，我们采用递归来构造
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return Recursion(nums, 0, nums.size() - 1);//平衡二叉搜索数，关键在于平衡两个字，左右数的高度差不超过1，搜索树，左节点小于 根节点 小于右节点//先谈平衡，我们找到数组的中间节点作为数的根节点，这个方法被论证过是可行的，然后我们要构建左右子树，//在根结点处将数组一分为二，考虑左节点，应该选取左半数组中的那个数？最大的？最小的？都不行，需要选中间的//左节点这颗子树也要是一颗平衡二叉搜索数，我们采用递归来构造}TreeNode* Recursion(vector<int>& nums, int left, int right){if (left > right){return nullptr;}int mid = (left + right) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = Recursion(nums, left, mid-1);root->right = Recursion(nums, mid+1, right);return root;}
};
