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;
}
}
};
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短