24ms solution using iterative BFS and some math


  • 0
    H
    void connect(TreeLinkNode *root) {
        if(root==nullptr) return;
        queue<TreeLinkNode*> myqueue;
        myqueue.emplace(root);
        TreeLinkNode* p;
        TreeLinkNode* q=nullptr;
        int count=0;
        int lcount=1;
        //We use a queue to perform a BFS
        while(!myqueue.empty()){
            count++;
            if(count==(2*lcount)){
                //case in which count is a power of two (and so p is the rightest vertex with this depth)
                q=nullptr;
                lcount *=2;
            }
            p = myqueue.front();
            p->next=q;
            myqueue.pop();
            if(p->right!=nullptr) myqueue.push(p->right);
            if(p->left!=nullptr) myqueue.push(p->left);
            q=p;
        }
    }

Log in to reply
 

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