第64天。
要死了,天天晚睡早起的,今天一定要早睡晚起(或者等下就睡睡先)
今天的题目是Convert Sorted Array to Binary Search Tree:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
这道题其实一开始没有思路的,感觉很难搞的样子,但是今天数据结构课上讲二分查找时提到了二分查找树(好像是这个名字),然后就觉得好像它就是一个height balanced BST
.
然后就仿照二分查找的递归算法解出了这道题,其实就是二分查找的逆过程:
1TreeNode* sortedArrayToBST(vector<int>& nums) {2 return sortedArrayToBST(nums,0,nums.size() - 1);3}4TreeNode *sortedArrayToBST(vector<int> &nums,int low,int high) {5 if (low > high) return nullptr;6 int mid = (low + high)/2;7 TreeNode *root = new TreeNode(nums[mid]);8 root->left = sortedArrayToBST(nums,low,mid-1);9 root->right = sortedArrayToBST(nums,mid+1,high);10 return root;11}