we could use Divide and Conquer.
we could do it recursively
pick the middle element as the root
then pass the left to the sortedArrayToBST, the array is from 0 to mid-1
pass the right to sortedArrayToBST, the array is from mid+1 the end
when the str is empty, return NULL
Several minor mistakes:
1. When debug in eclipse, you should always check if you have include the corresponding headers, or you would got strange errors(error: expected ‘;’ at end of member declaration).
2. DO NOT FORGET THE RETURN VALUE IN IF-ELSE CONDITION!
96 milli secs to pass Judge Large
class Solution { public: TreeNode* sortedArrayToBSTHelper(int* arr, int start, int end) { if (start <= end) { int len = end - start; int mid = start + len / 2; TreeNode* root = new TreeNode(arr[mid]); root->left = sortedArrayToBSTHelper(arr, start, mid - 1); root->right = sortedArrayToBSTHelper(arr, mid + 1, end); return root; } else return NULL; }; TreeNode* sortedArrayToBST(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function if (num.empty()) return NULL; int arr[num.size()]; for (int i = 0; i < num.size(); i++) { arr[i] = num[i]; } return sortedArrayToBSTHelper(arr, 0, num.size() - 1); }; };