二叉搜索树是一颗特殊的二叉树，它满足以下条件：
- 若左子树非空，则左子树所有节点的值一定小于根节点
- 若右子树非空，则右子树所有节点的值一定大于等于根节点
- 左右子树也都是二叉搜索树
显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。
但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同：
- 若左子树非空，则左子树所有节点的值一定小于根节点
- 若右子树非空，则右子树所有节点的值一定大于等于根节点
- 左子树与右子树的高度差的绝对值小于等于1
- 左右子树也都是平衡二叉搜索树
同时定义平衡因子为节点左子树与右子树深度之差。
那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* build(vector<int>& nums, int l, int r)
{
if (r < l) return nullptr;
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode;
root->val = nums[mid];
root->left = build(nums, l, mid - 1);
root->right = build(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
};