LintCode-排序列表转换为二分查找树分析及实例
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
您在真实的面试中是否遇到过这个题？
分析：就是一个简单的递归，只是需要有些链表的操作而已
代码：
/**
*DefinitionofListNode
*classListNode{
*public:
*intval;
*ListNode*next;
*ListNode(intval){
*this->val=val;
*this->next=NULL;
*}
*}
*DefinitionofTreeNode:
*classTreeNode{
*public:
*intval;
*TreeNode*left,*right;
*TreeNode(intval){
*this->val=val;
*this->left=this->right=NULL;
*}
*}
*/
classSolution{
public:
/**
*@paramhead:Thefirstnodeoflinkedlist.
*@return:atreenode
*/
TreeNode*sortedListToBST(ListNode*head){
//writeyourcodehere
if(head==nullptr)
returnnullptr;
intlen=0;
ListNode*temp=head;
while(temp){len++;temp=temp->next;};
if(len==1)
{
returnnewTreeNode(head->val);
}
elseif(len==2)
{
TreeNode*root=newTreeNode(head->val);
root->right=newTreeNode(head->next->val);
returnroot;
}
else
{
len/=2;
temp=head;
intcnt=0;
while(cntnext;
cnt++;
}
ListNode*pre=head;
while(pre->next!=temp)
pre=pre->next;
pre->next=nullptr;
TreeNode*root=newTreeNode(temp->val);
root->left=sortedListToBST(head);
root->right=sortedListToBST(temp->next);
returnroot;
}
}
};
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！