Convert Sorted Array to Binary Search Tree

Nov 30, 2017

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

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

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;
}
LeetCodeLeetCode

Swaps-Nodes-in-Pairs

Path-Sum

comments powered by Disqus