Give my solution to reference. O(N + 1/2NlogN) time, no extra space, but recursive.( welcome discuss)


  • 0
    L
    ListNode* findMiddleNode(ListNode *head, int length) {
        if(length <= 0) return NULL;
        int mid = (length+1) / 2;
        for(int i = 1; i < mid; ++i) head = head->next;
        return head;
    }
    int getLength(ListNode *head) {
        int ans = 0;
        while(head) { ans++; head = head->next; }
        return ans;
    }
    TreeNode* createBST(ListNode *head, int length) {
        ListNode *pMid = findMiddleNode(head, length);
        TreeNode *root = NULL;
        if(pMid) {
            root = new TreeNode(pMid->val); 
            root->left = createBST(head, (length-1) >> 1);
            root->right = createBST(pMid->next, length / 2);
        }
        return root;
    }
    class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head) {
            return createBST(head, getLength(head));
        }
    };
    

    Thoughts: Every time select the middle list Node to creat current BST Node, the tree will be balanced automatically.


  • 2
    Y

    you can try this?

    class Solution {
    public:
        TreeNode *helper(ListNode *head, ListNode *tail) {
            if (head == NULL) return NULL;
            ListNode *n1 = head;
            ListNode *n2 = head;
            while (n2 != tail && n2->next != tail) {
                n1 = n1->next;
                n2 = n2->next->next;
            }
            TreeNode * tn = new TreeNode(n1->val);
            tn->left = helper((head == n1) ? NULL : head, n1);
            tn->right = helper((n1->next == tail) ? NULL : n1->next, tail);
            return tn;
        }
        TreeNode *sortedListToBST(ListNode *head) {
            if (head == NULL) return NULL;
            return helper(head, NULL);
        }
    };

  • 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


  • 5
    V

    Your method constructs the tree from root to leaves and its time complexity is O(nlogn).

    To optimize we need to change the strategy by constructing the tree from leaves to root, to do that insert nodes in BST in the same order as the appear in Linked List, by doing so the time complexity would be simply O(n) as we just need to traverse the linked list.

    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.

    NOTE :: While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.

    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
    L

    I don't think your Solution is right ! { Befor "root->left = left", you set a new local variant "root = NULL" which may be a bug.}. By the way, your answer is similiar with mine but just down the recursive depth to (log2N - log2(N/2)) which is no need.


  • 0
    G

    that is just a mistake by hand, it should be create a new node for root ,and set it value with the current head, then everything will be alright


  • 0
    V

    Please find this debugged code, and the time complexity of this program is O(n), as in this code there is no overhead of finding the middle of linked list node due to that time complexity has reduced from O(nlogn) to O(n).


  • 0
    L

    Time complexity is same as above.


  • 0
    W

    I like the way @vivek.bits puts, and its right. Build the tree from the leaf is a good method, and I think @liyangguang1988 should notice the method solving the problem, not only the time complexity. Yeah, my method is same to you, from the root to leaf.


Log in to reply
 

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