[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.

分治是比较好而且容易想到的思路。

 1 class Solution {
 2 public:
 3     TreeNode *mergeAToT(vector<int> &num,int left,int right){
 4         if(left>right)
 5             return NULL;
 6         int mid = (right+left)/2;
 7         TreeNode *node = new TreeNode(num[mid]);
 8         node->left = mergeAToT(num,left,mid-1);
 9         node->right = mergeAToT(num,mid+1,right);
10         return node;
11     }
12     TreeNode *sortedArrayToBST(vector<int> &num) {
13         return mergeAToT(num,0,num.size()-1);
14     }
15 };