Monday, April 22, 2013
Leetcode: Convert Sorted List to Binary Search Tree in C++
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
TreeNode *ToBST(ListNode *& current,int start, int end)
{
if(start>end)
return NULL;
int mid = start + (end-start)/2;
TreeNode* left = ToBST(current,start,mid-1);
TreeNode* n1 = new TreeNode(current->val);
n1->left = left;
current = current->next;
n1->right = ToBST(current,mid+1,end);
return n1;
}
TreeNode *sortedListToBST(ListNode *head) {
if(!head)
return NULL;
ListNode* p = head;
int count =0;
while(p)
{
count++;
p = p->next;
}
return ToBST(head,0,count-1);
}
Labels:
Botton up
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment