Sorted List to binary search tree O(nlogn) time complexity


  • 1
    N
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return new TreeNode(head->val);
        ListNode *step1 = head;
        ListNode *step2 = head->next;
        while(step2->next != NULL && step2->next->next != NULL){
            step1 = step1->next;
            step2 = step2->next->next;
        }
        TreeNode *root  = new TreeNode(step1->next->val);
        ListNode *head2 = step1->next->next;
        delete step1->next;
        step1->next = NULL;
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(head2);
        return root;
    }

  • 12
    V

    Do bottom up approach and construct the tree from the leaves rather than doing top down approach and constructing tree from root to get o(n) time complexity.

    STEP 1: Take left n/2 nodes and recursively construct the left sub tree.

    STEP 2: After left sub tree is constructed, we allocate memory for root and link the left sub tree with root.

    STEP 3: Finally, we recursively construct the right sub tree and link it with root.

    class Solution {
    public:
        ListNode *list;
        int lengthOfList(ListNode *node){
            int length = 0;
            while (node) {
                length++;
                node = node->next;
            }
            return length;
        }
        TreeNode *populateTree(int n){
            if (n == 0)
                return NULL;
            TreeNode *treenode = new TreeNode(0);
            treenode->left = populateTree(n / 2);
            treenode->val = list->val;
            list = list->next;
            treenode->right = populateTree(n - n / 2 - 1);
            return treenode;
        }
        TreeNode *sortedListToBST(ListNode *head) {
            this->list = head;
            return populateTree(lengthOfList(head));
        }
    };

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    C

    I think it is O(n^2)


Log in to reply
 

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