[C++] Surprisingly fast, 23ms (beats 90% of the submissions), O(1) solution.


  • 0
    V
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(root == nullptr || (root->left == nullptr && root->right == nullptr)) return;
            
            TreeLinkNode* curr = root;
            TreeLinkNode* prev = nullptr;
            TreeLinkNode* first = nullptr;
            
            while(curr != nullptr){
                if(curr->left != nullptr){
                    if(prev == nullptr){
                        first = curr->left; // Store the first node of the new level
                    }
                    else{
                        prev->next = curr->left;
                    }
                    prev = curr->left;
                }
                
                if(curr->right != nullptr){
                    if(prev == nullptr){
                        first = curr->right; // Store the first node of the new level
                    }
                    else{
                        prev->next = curr->right;
                    }
                    prev = curr->right;
                }
                curr = curr->next;
                if(curr == nullptr){ // reached the end of current level
                    curr = first; // Go to next level
                    first = nullptr; // reset the first node of the new level
                    prev = nullptr;
                }
            }
        }
    };
    

Log in to reply
 

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