O(n) complexity, but O(log n) memory space


  • 1
    H
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(root == NULL) return;
            queue<pair<TreeLinkNode*, int> > q;
            q.push(make_pair(root,0));
            while(!q.empty()) {
                TreeLinkNode* x = q.front().first;
                int depth = q.front().second;
                q.pop();
                if (q.empty() || q.front().second != depth) {
                    x->next = NULL;
                } else {
                    x->next = q.front().first;
                }
                if (x->left != NULL) {
                    q.push(make_pair(x->left,depth + 1));
                } 
                if (x->right != NULL) {
                    q.push(make_pair(x->right,depth + 1));
                }
            }
        }
    };
    

    The idea of this code is just broad first search and keep track on depth of each vertex. When we know the depth of a vertex we can find out where "Next" should point.
    But the problem is that in statement's notes was mentioned that we could use only constant extra space.
    Here I use at most O(log n) - because in binary tree each level contains at most O(log n) vertexes and in each moment I contain only at most two levels in queue. Therefore, I get O(log n) memory complexity. Couldn't find out how to rid off in my algorithm of this memory or find another approach.
    Thanks for any answers.


  • 0
    S

    Could you please format your code correctly? Select a code block and click on the {} button to preserve code formatting.


  • 2
    T

    Just do a level-order traverse.


  • 1
    W

    For each node from root on, find the sibling through parent and parent's siblings, then link it; if the sibling is NULL, then go to the next level. So you also need to keep book on first node of next level, and its parent. When the first node of next level is NULL, you can finish the operation. Time complex O(n), space O(1):

    class Solution {
    public:
    void connect(TreeLinkNode *root) {
            TreeLinkNode * p = NULL;
            TreeLinkNode * c = root;
            TreeLinkNode * ch = c;
            TreeLinkNode * s = NULL;
            TreeLinkNode * nh = NULL;
            for(;c;s = NULL){
                //set children head
                if(!nh){
                    if(c->left)
                        nh = c->left;
                    else
                        nh = c->right;
                    if(nh)
                        ch = c;
                }
                //find sibling
                if(p){
                    if(p->left == c)
                        s = p->right;
                    while(!s){
                        p = p->next;
                        if(!p)
                            break;
                        if(p->left)
                            s = p->left;
                        else
                            s = p->right;
                    }
                }
                if(s){  //move to sibling
                    c->next = s;
                    c = s;
                }else{  //move to children
                    p = ch;
                    c = nh;
                    ch = nh = NULL;
                }
            }
        }
    };

  • 0
    C

    I think the space should be O(n), as if the tree is full binary tree, the last level will have O(n/2) nodes if the total number of nodes is n.


  • 0
    D

    Yes, the space is O(N)


Log in to reply
 

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