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; } } };
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!