Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
class Solution {
TreeNode *sortedListToBST(ListNode *&head, int start, int end)
{
if (start > end) return NULL;
int m = (start + end)/2;
TreeNode *left = sortedListToBST(head, start, m-1);
TreeNode *root = new TreeNode(head->val);
root->left = left;
head = head->next;
root->right = sortedListToBST(head, m+1, end);
return root;
}
public:
TreeNode *sortedListToBST(ListNode *head) {
int count = 0;
ListNode *p = head;
while(p) {
count++;
p = p->next;
}
return sortedListToBST(head, 0, count-1);
}
};
TreeNode *sortedListToBST(ListNode *head) {
if (!head) return NULL;
if (!head->next) return new TreeNode(head->val);
ListNode *p = head;
ListNode *pp = head->next;
while(pp->next && pp->next->next) {
p = p->next;
pp = pp->next->next;
}
pp = p->next;
p->next = NULL;
TreeNode *root = new TreeNode(pp->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(pp->next);
return root;
}
No comments:
Post a Comment