Share my code with O(n) time and O(1) space


  • 74
    V

    count is a function to calculate the size of list.

    Key words: inorder traversal.

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

  • 0
    V

    Considering the fact that the program is not tail recursive it will have the overhead of call stack space and hence space complexity is O(n) for n recursive calls.


  • 40
    E

    The space complexity of your solution is obviously not constant since you used recursion here. I think it should be O(logn) (overhead used by the recursion, not including space used by the nodes) .


  • 0
    A

    Good solution.


  • 0
    S

    Beautifully done.


  • 3
    S

    Good point. I've seen too many people in this forum claiming their recursive solution to take O(1) space.
    As a rule of thumb, a recursive program almost NEVER has O(1) space complexity:)


  • 1
    S

    It should be O(n), because n new tree nodes were created. The overhead of recursive function call is O(log(n)).


  • 0
    E

    Yeah you are right. Actually I meant the additional space besides space used by the tree nodes was O(log(n)).


  • 0
    B

    It is very awesome code. I wonder how you came up with this idea? Can you tell me if there is a mathematical theorem or something? Thank you very much!


  • 3

  • 0
    A

    I cannot see any benefit of using this solution. The tricky part is not using extra space. If we are allowed to use extra O(n) space. We can simply copy the data in the list to an array and create a balanced tree from there.


  • 0
    X

    awesome solution


  • 2
    I

    i have a question, pls help!!!
    why the time complexity is O(n) rather than O(nlogn) ?
    the each node n/pow(2, x) traverse.. and we have n nodes...


  • 0
    I

    why this solution ran slower than others with O(nlogn) ????


  • -1
    R
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            TreeNode* root;
            int len=length(head);
            sortedListToBST(root, head, len);
            return root;
        }
    private:
        void sortedListToBST(TreeNode* &root, ListNode* &head, int len){
            if(len<=0){
                root=NULL;
                return;
            }
            TreeNode* left;
            sortedListToBST(left, head, len/2);
            
            root=new TreeNode(head->val);
            head=head->next;
            root->left=left;
            
            sortedListToBST(root->right, head, len-len/2-1);
        }
        int length(ListNode* head){
            int len=0;
            while(head!=NULL){
                len++;
                head=head->next;
            }
            return len;
        }
    };

  • 0
    Y

    I think the solution use reference can be more clear.


  • 2
    Y

    Solution using reference.Is there any benifits?

    BTW:I think the time comlexity is O(N),and the space complexity is O(logN).

    class Solution
    {
    public:
        TreeNode* sortedListToBST(ListNode* head)
        {
            return helper(count(head),head);
        }
    private:
        int count(ListNode *node)
        {
            int len=0;
            while(node)
            {
                ++len;
                node=node->next;
            }
            return len;
        }
        //here we use reference to a pointer instead of a global variable.
        TreeNode *helper(int len,ListNode* &cur)
        {
            if(len==0)
                return nullptr;
            TreeNode *node=new TreeNode(0);
            node->left=helper(len/2,cur);
            node->val=cur->val;
            cur=cur->next;
            node->right=helper(len-len/2-1,cur);
            return node;
        }
    };

  • 0
    B

    very good code.


  • 0
    E

    I also had this doubt as my solution is also a recursive one.


  • 0
    L

    I like your key words, that's the point!


Log in to reply
 

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