这篇文章给大家分享的是有关LintCode如何实现排序列表转换为二分查找树的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
您在真实的面试中是否遇到过这个题？
分析：就是一个简单的递归，只是需要有些链表的操作而已
代码：
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
// write your code here
if(head==nullptr)
return nullptr;
int len = 0;
ListNode*temp = head;
while(temp){len++;temp = temp->next;};
if(len==1)
{
return new TreeNode(head->val);
}
else if(len==2)
{
TreeNode*root = new TreeNode(head->val);
root->right = new TreeNode(head->next->val);
return root;
}
else
{
len/=2;
temp = head;
int cnt = 0;
while(cnt<len)
{
temp = temp->next;
cnt++;
}
ListNode*pre = head;
while(pre->next!=temp)
pre = pre->next;
pre->next = nullptr;
TreeNode*root = new TreeNode(temp->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(temp->next);
return root;
}
}
};
感谢各位的阅读！关于“LintCode如何实现排序列表转换为二分查找树”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
