LeetCode108 Convert Sorted Array to Binary Search

By | 19/03/2018

【题目】:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

 

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

 

【Code】:

class Solution{

public:

TreeNode* sortedArrayToBST(vector<int> & nums){

returnfunc(nums,0,nums.size()-1);

}

private:

TreeNode* func(vector<int> &nums, int left, int right){

if(left>right){

returnNULL;

}

int mid = (left+right)/2;//因为排序好了 所以中间的就是BST的根

TreeNode* root = new TreeNode(nums[mid]);

root->left = func(nums,0,mid-1);//左子树

root->right = func(nums,mid+1,nums.size()-1);

return root;

}

};

 

【遇到的问题和解决办法】:

这一题感觉没什么难度,因为他没有说所以的二叉树情况,只是说了给出一种二叉树的情况即可那么,二叉树的中间节点即是当前数组的中间为数组,而且这个地方非常好的就是它居然还给我排列好的数组简直美滋滋有木有,好了根确定了之后那么就可以利用递归把左右子树通过类似的方式向下递归了。

发表评论