Concise cpp solution beating most of others, with comments.


  • 0
    S
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root)  return;
            TreeLinkNode *p = root,*pre;
            while(p){
                if(p->left)  pre = p->left;
                else pre = p->right;
                for(auto curr = p; curr; curr = curr->next){
                    if(!curr->left && !curr->right)  continue;  // skip the leaf node
                    if(curr->left && curr->left != pre) { pre->next = curr->left;  pre = curr->left;  }
                    if(curr->right && curr->right != pre){ pre->next = curr->right;  pre = curr->right; }
                }
                while(p && !p->left && !p->right) p = p->next; // find the first node having at least one child
                if(!p)  return;
                p = p->left ? p->left : p->right;
                while(p && !p->left && !p->right) p = p->next;  // in order to find the first position of pre in next loop.
            }
            return ;
        }
    };

Log in to reply
 

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