题目链接：Convert Sorted Array to Binary Search Tree

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

这道题的要求是将有序数组转化成高度平衡的二叉搜索树（BST）。

由于数组有序，因此相当于二叉搜索树的前序遍历。又由于要求二叉搜索树高度平衡，即左右子树高度相差小于等于1，所以取数组中间的数作为根节点，左边作为左子树，右边作为右子树，这样就可以构造出高度平衡的二叉搜索树了。

这样，思路就和Construct Binary Tree from Preorder and Inorder Traversal以及Construct Binary Tree from Inorder and Postorder Traversal差不多，都是递归构造左右子树即可。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution 
{
public:
    TreeNode *sortedArrayToBST(vector<int> &num) 
    {
        return sortedArrayToBST(num, 0, num.size() - 1);
    }
private:
    TreeNode *sortedArrayToBST(vector<int> &num, int l, int r)
    {
        if(l > r)
            return NULL;
        
        int m = (l + r) / 2;
        TreeNode *root = new TreeNode(num[m]);
        root -> left = sortedArrayToBST(num, l, m - 1);
        root -> right = sortedArrayToBST(num, m + 1, r);
        return root;
    }
};