Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
http://blog.csdn.net/linhuanmars/article/details/23904883
Time: O(n)
Space: O(n)+O(logn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return helper(nums, 0, nums.size() - 1); } TreeNode* helper(vector<int>& nums, int left, int right){ if(left > right) return NULL; int mid = (left + right) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = helper(nums, left, mid - 1); root->right = helper(nums, mid + 1, right); return root; } }; |
没有评论:
发表评论