[LeetCode] Convert Sorted Array to Binary Search Tree, Solution

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

» Solve this problem

[Thoughts]
If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST via left part array
3. build right sub BST via right part array
4. do this recursively.


[Code]

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