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);
        
    }

No comments:

Post a Comment