Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
» Solve this problemComplexity: O(n)
/** * 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&num) { // Start typing your C/C++ solution below // DO NOT write int main() function return toBST(num, 0, num.size() - 1); } TreeNode *toBST(vector &num, int start, int end) { if (end < start) { return NULL; } int mid = (start + end) / 2; TreeNode *root = new TreeNode(num[mid]); root->left = toBST(num, start, mid - 1); root->right = toBST(num, mid + 1, end); return root; } };
No comments:
Post a Comment