Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
47 lines (40 sloc) 1.1 KB
problem:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
--------------------------------------------------------------------
solution:
///////////////////////////////////////////////
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//由于链表不能随机读取,因而用上题的解决方案不是很便捷,这里考虑从底向上建树
TreeNode *sortedListToBST_aux(ListNode *&head, int begin, int end)
{
if(begin > end)
return NULL;
int mid = (begin + end) / 2;
TreeNode *leftChild = sortedListToBST_aux(head, begin, mid - 1);
TreeNode *parent = new TreeNode(head->val);
parent->left = leftChild;
head = head->next;
parent->right = sortedListToBST_aux(head, mid + 1, end);
return parent;
}
TreeNode *sortedListToBST(ListNode *head)
{
int len = 0;
ListNode *p = head;
while(p)
{
len++;
p = p->next;
}
return sortedListToBST_aux(head, 0, len - 1);
}