Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
本题是二分法的高级应用，每次选择root都是从数列的中间选择，那么最后构造出来的二叉树一定是高度平衡的BST了。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *sortedArrayToBST(vector<int> &num)
{
return biSortedArrayToBST(num, 0, num.size()-1);
}
TreeNode *biSortedArrayToBST(vector<int> &num, int low, int up)
{
if (low > up) return NULL;
int mid = low + ((up-low)>>1);
TreeNode *r = new TreeNode(num[mid]);
r->left = biSortedArrayToBST(num, low, mid-1);
r->right = biSortedArrayToBST(num, mid+1, up);
return r;
}
};