Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
思路：使用二分法，将list的中间节点作为根节点，然后分别处理list左半边及右半边，以此递归。
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) {
if(num.empty()) return NULL;
TreeNode* root = new TreeNode();
dfs(num,,num.size()-,root);
return root;
}
void dfs(vector<int> &num,int start, int end,TreeNode* treeNode)
{
int size = end-start+;
if(size == )
{
treeNode->val = num[start];
return;
}
int mid = size/ + start;
treeNode->val = num[mid];
treeNode->left = new TreeNode();
dfs(num,start,mid-,treeNode->left);
if(mid+<=end)
{
treeNode->right = new TreeNode();
dfs(num,mid+,end,treeNode->right);
}
}
};