Online Judge Solutions

Friday, January 2, 2015

Convert Sorted List to Binary Search Tree

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