Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
这个链接给出了这个题目的完美解法:http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
链接里有详细的介绍,有需要的话可以移步参阅。这个递归解法其实跟这个题目http://blog.csdn.net/chfe007/article/details/42153475的解题思路是一样的,只是由于链表和数组的不同导致解法上的不同。C++代码实现如下:
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
return head ? sortedListToBSTHelper(&head, , getLength(head) - ) : nullptr;
}
private:
int getLength(ListNode *head)
{
int len = ;
for (ListNode *node = head; node != nullptr; node = node->next, ++len);
return len;
}
TreeNode *sortedListToBSTHelper(ListNode **head, int start, int end)
{
if (*head == nullptr || end < start) return nullptr;
int mid = (start + end) >> ;
TreeNode *root = new TreeNode();
root->left = sortedListToBSTHelper(head, start, mid - );
root->val = (*head)->val;
*head = (*head)->next;
root->right = sortedListToBSTHelper(head, mid + , end);
return root;
}
};
这种解法的时间性能如下图所示: