My Accepted C++ solution


  • 59
    A
    class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head)
        {
        	return sortedListToBST( head, NULL );
        }
        
    private:
        TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
        {
        	if( head == tail )
        		return NULL;
        	if( head->next == tail )    // 
        	{	
        		TreeNode *root = new TreeNode( head->val );
        		return root;
        	}
        	ListNode *mid = head, *temp = head;
        	while( temp != tail && temp->next != tail )    // 寻找中间节点
        	{
        		mid = mid->next;
        		temp = temp->next->next;
        	}
        	TreeNode *root = new TreeNode( mid->val );
        	root->left = sortedListToBST( head, mid );
        	root->right = sortedListToBST( mid->next, tail );
        	return root;
        }
    };

  • 0
    M

    clever way to find the middle of the list :)


  • 1
    G

    I have a question, please help.

    when you find the mid node and using the val to construct a root TreeNode, but when you construct the left tree, why don't you delete the mid node ?


  • 1
    M

    No need. It won't be really get to the tail. Look carefully at the base case and you will know.


  • 0
    L

    adding tail param makes the program clear.
    better comment it in english


  • 1
    K

    T(n) = 2T(n/2) + n
    Apply the master method,O(n) = nlog(n)....


  • 0
    R

    can you tell me space and time complexity?


  • 0
    R

    can you tell me space and time complexity?


  • 4
    Q
    if( head->next == tail )    // 
            {   
                TreeNode *root = new TreeNode( head->val );
                return root;
            }
    

    this part is unecessary


  • 1
    H
    if( head->next == tail )    // 
    {   
        TreeNode *root = new TreeNode( head->val );
        return root;
    }
    

    is unnecessary.


  • 0
    C
    This post is deleted!

  • 0
    L

    The way to find the mid point of a linked list is very enlightening.


  • 0
    J

    Great solution with the fast-slow pointer!


  • 1
    W

    Good solution, but we can do better. Following shorter solution runs 22ms:

    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);
        auto fast = head->next, slow = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        auto mid = slow->next;
        slow->next = nullptr;
        auto root = new TreeNode(mid->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(mid->next);
        return root;
    }
    

  • 1
    L

    @wfxr 破坏了输入数据 如果在多线程环境下 可能比较危险


  • 0
    S
    This post is deleted!

  • 1
    J

    The step of finding the mid node is really amazing~


  • 0
    S

    @Jenny sorry that was a mistake. It's not my own answer but an incorrect reply after I copied the answer and tried to submit. And the most awkward thing was that because of my insufficient privilege, I was even not able to purge it. =_=


Log in to reply
 

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