[LeetCode] Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

将一个有序的数组转换为一棵高度平衡的二叉树。这道题像中序遍历的逆过程。所以先找到数组中中间位置的值作为树根元素。然后将数组分为两个部分，递归的找出各个子树的根节点即可。

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