传送门

二叉搜索树是一颗特殊的二叉树，它满足以下条件：

  1. 若左子树非空，则左子树所有节点的值一定小于根节点
  2. 若右子树非空，则右子树所有节点的值一定大于等于根节点
  3. 左右子树也都是二叉搜索树

显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。

但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同：

  1. 若左子树非空，则左子树所有节点的值一定小于根节点
  2. 若右子树非空，则右子树所有节点的值一定大于等于根节点
  3. 左子树与右子树的高度差的绝对值小于等于1
  4. 左右子树也都是平衡二叉搜索树

同时定义平衡因子为节点左子树与右子树深度之差。

那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。

/**
 * 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);
    }
};