Clean C++ solution. Recursion. O(nlogn). With comment


  • 23
    Z

    Recursively build tree.

    1. find midpoint by fast/slow method, use middle node as root.
    2. build left child by first half of the list
    3. build right child by second half of the list (head is midpoint->next)
    <cpp>
        class Solution {
        public:
            TreeNode *sortedListToBST(ListNode *head) {
                if(!head) return NULL;
                if(!head->next) return new TreeNode(head->val);
                
                // fast/slow pointer to find the midpoint
                auto slow = head;
                auto fast = head;
                auto pre = head;
                while(fast && fast->next) {
                    pre = slow;
                    slow = slow->next;
                    fast = fast->next->next;
                }
                pre->next = 0; // break two halves 
                
                // slow is the midpoint, use as root
                TreeNode* root = new TreeNode(slow->val);
                root->left = sortedListToBST(head);
                root->right = sortedListToBST(slow->next);
                
                return root;
            }
        };

  • 0
    9

    cool solution !!!


  • 4

    we share the same idea, but in my solution, pre is not needed:

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (head == NULL)
                return NULL;
            if (head->next == NULL)
                return new TreeNode(head->val);
            ListNode *fast = head->next->next, *slow = head;
            while (fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            TreeNode* root = new TreeNode(slow->next->val);
            root->right = sortedListToBST(slow->next->next);
            slow->next = NULL;
            root->left = sortedListToBST(head);
            return root;
        }
    };

  • 0
    S

    I don't think it's a proper way to solve the problem, though you can temporarily "solve" it in OJ. After constructing the tree, the list will be destroyed permanently. It causes serious memory leak, which can't be permitted in C++ programming.


  • 0
    A

    Can you share some light on why will the code above will destroy the original list?


  • 1
    S

    pre->next = 0;
    This statement will disconnect the two nodes. After building the tree, you can try to traverse the "list" from head and you will find there's only one node in the "list". Where are others? They are in the memory but you can no longer find them.
    If you doesn't get it, you can try it and you will understand then.


  • 0
    A

    You are right, I never thought of that, previously I think that we can still access list from head pointer. Thank you.


  • 0
    C

    The title of this problem is Convert Sorted List to Binary Search Tree. So I think we no longer need to access the original list after the conversion.


  • 0
    R

    I did this by counting the number of nodes and making a separate case for even and odd number of nodes.
    This does not destroy the linked list. And there is no memory loss.

     TreeNode* bst (ListNode* head, int n) {
        if (n<=0) return NULL;
        if (n==1) {
            TreeNode* root = new TreeNode(head->val);
            return root;
        }
        /* To get to the middle point, traverse the list*/
        int count=0; 
        ListNode* current = head;
        while (current!=NULL && count<(n/2-1)) {
            current = current->next;
            count++;
        }
       /*if even nodes are there*/
        if (n%2==0) { 
            TreeNode* root = new TreeNode(current->val);
            root->left = bst(head,n/2-1);
            root->right = bst(current->next,n/2);
            return root;
        }
         /*if odd nodes are there*/
        else { 
            TreeNode* root = new TreeNode(current->next->val);
            root->left = bst(head,n/2);
            root->right = bst(current->next->next,n/2);
            return root;
        }
    }
    
    TreeNode* sortedListToBST(ListNode* head) {
        if (head==NULL) return NULL;
        ListNode* current = head;
     /*First getting the total number of nodes in list*/
        int count = 0;
        while (current!=NULL) { 
            current=current->next;
            count++;
        }
        return (bst(head,count));
    }

  • 0

    I have the simliar idea. But I meet a problem that I used to use the dummy node to find the middle node.

    So I have implemented almost the same code except that I use the dummy node to find the middle node.

    So the only difference happens when the linked-list length is even. My implementation find the left middle

    pointer while you find the right pointer. So I will meet the corner case. So I am wondering any one can

    help me solve the corner cases with dummy pointer coding style.

    Thank you very much !

     class Solution {
        public:
            TreeNode* sortedListToBST(ListNode* head) {
                if(!head)   return NULL;
                if(!head->next)  return new TreeNode(head->val);
                
                ListNode *dummy = new ListNode(-1);
                dummy->next=head;
                /** find the middle pointer **/
                ListNode *slow=dummy, *fast=dummy;
                while(fast && fast->next){
                    slow=slow->next;
                    fast=fast->next->next;
                }
                
                /** set the pointer previous to the middle pointer point to NULL **/
                ListNode *temp=dummy;
                while(temp->next!=slow){
                     temp=temp->next;   
                }
                temp->next=NULL;
                
                /** revursively build the BST  **/
                ListNode *left=head, *right=slow->next;
                TreeNode *root = new TreeNode(slow->val);
                root->left=sortedListToBST(left);
                root->right=sortedListToBST(right);
                return root;
            }
        };

  • 0
    S

    use pointer to pointer

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

  • 0
    Z

    @StrayWarrior You are right, but we can easily fix this issue by first copy a same list from head , then call this function.For memory leak issue we can call delete the slow->next node to deallocate it. So there is no problem with the algorithm, but we need to consider more detail when implement it,isn't it?


  • 0
    P
    • @RainbowSecret try using: slow = head, fast = head->next; then slow is always the middle node, use prev which starts from dummy, prev is the former node of middle. like this:
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(!head)   return NULL;
            if(!head->next) return new TreeNode(head->val);
            ListNode *dummy = new ListNode(-1),*p1 = head, *p2 = head->next, *prev;
            dummy->next = head; prev = dummy;
            while(p2 && p2->next){
                p1 = p1->next;
                p2 = p2->next->next;
                prev = prev->next;
            }
            prev->next = NULL;
            TreeNode *root = new TreeNode(p1->val);
            root->left = sortedListToBST(dummy->next);
            root->right = sortedListToBST(p1->next);
            return root;
        }
    };
    

Log in to reply
 

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