Convert Sorted Array to Binary Search Tree

LeetCode

第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.

然后就仿照二分查找的递归算法解出了这道题，其实就是二分查找的逆过程：

1
2
3
4
5
6
7
8
9
10
11
TreeNode* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBST(nums,0,nums.size() - 1);
}
TreeNode *sortedArrayToBST(vector<int> &nums,int low,int high) {
    if (low > high) return nullptr;
    int mid = (low + high)/2;
    TreeNode *root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums,low,mid-1);
    root->right = sortedArrayToBST(nums,mid+1,high);
    return root;
}