Both O(n) and O(nlogn) code :D


  • 0
    N
    
    // O(n) solution little bit tricky
    TreeNode *GiantConvert(ListNode *&head,int start,int end)
    {
        if(start>end)   return NULL;
        int mid = (start+end)>>1;
        TreeNode *Left = GiantConvert(head,start,mid-1);
        TreeNode *parent = new TreeNode(head->val);
        parent->left = Left;
        head = head->next;
        parent->right = GiantConvert(head,mid+1,end);
        return parent;
    }
    
    //O(nlogn) solution simple and intuitive
    TreeNode *freeConvert(ListNode *head,int start,int end)
    {
        if(start>end)   return NULL;
        int mid = (start+end)>>1;
        ListNode *temp = head;
        for(int i=0;i<mid;i++){
            temp = temp->next;
        }
        TreeNode *root = new TreeNode(temp->val);
        root->left = freeConvert(head,start,mid-1);
        root->right = freeConvert(head,mid+1,end);
        return root;
    }
    
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            int l = 0;
            ListNode *temp = head;
            while(temp){
                l++;
                temp = temp->next;
            }
            // TreeNode *root = GiantConvert(head,0,l-1);
            TreeNode *root = freeConvert(head,0,l-1);
            return root;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.