Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
本来想在递归中不用for循环把问题解决点，想了很久不知道该怎么做，看了网上的答案，发现大家就是用的循环·····
用循环的话，就非常简单了，但是我写代码的时候，子函数用引用传参数的时候报错，不知道为啥，可能是默认的编译器的问题··
代码很简单，如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* 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:
int getLength(ListNode* &head)
{
int len=;
ListNode* p=head;
if(p==NULL)
return ;
else
{
len=;
while(p->next!=NULL)
{
len++;
p=p->next;
}
}
return len;
}
// TreeNode*getSubBST(ListNode* head,int &left,int &right)
TreeNode*getSubBST(ListNode* head,int left,int right)
{
if(left>right)
return NULL;
else
{ ListNode* p=head;
int mid=(left+right)/;
for(int i=left;i<mid;i++)
p=p->next;
TreeNode* node=new TreeNode(p->val);
node->left=getSubBST(head,left,mid-);
node->right=getSubBST(p->next,mid+,right);
return node;
}
}
TreeNode* sortedListToBST(ListNode* head) {
TreeNode* res;
int len=getLength(head);
res=getSubBST(head,,len-);
return res; }
};
Convert Sorted Array to Binary Search Tree（有了上面这道题的基础，这道题就非常简单了，直接搬过来就能用了。）
这道题思想其实是特别的简单，实现起来居然试了很多次才对，再次体现了我的代码能力不足，这道题就是很简单的递归，每次去除中间的数，剩余的两边采用递归构造子树。
把数组切分成左右两部分我采用了vector中迭代器赋值的方法，结果在里面倒腾了很久，其实不用迭代器也行，网上许多的代码都比我的精简，再次说明我的代码能力不足，思维不够开阔··················
我的代码：
/**
* 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) {
TreeNode* res=NULL;
int len=nums.size();
if(len==)
return NULL;
else if(len==)
{
res=new TreeNode(nums[]);
return res;
}
else
{
int flag;
vector<int>::iterator root;
if(len%==)
{
root=nums.begin()+len/-;
flag=len/-;
}
else
{
root=nums.begin()+len/;
flag=len/;
} res=new TreeNode(*root);
int LeftStart=;
int LeftEnd=flag;
vector<int> subNumsL(nums.begin(),root);
int RightStart=flag+;
int RightEnd=len-;
vector<int> subNumsR(root+,nums.end());
if( LeftStart<LeftEnd)
res->left=sortedArrayToBST(subNumsL);
if(RightStart<=RightEnd)
res->right=sortedArrayToBST(subNumsR);
}
return res;
}
};
网上比较精简的代码：
class Solution
{
public:
void build(vector<int> &num, TreeNode * &root, int left, int right)
{
if(left>right)
return;
int mid = (left+right)/;
root = new TreeNode(num[mid]);
build(num, root->left, left, mid-);
build(num, root->right, mid+, right);
}
TreeNode *sortedArrayToBST(vector<int> &num)
{
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = num.size();
TreeNode * root = NULL;
if(len>)
build(num, root, , len-);
return root;
}
};