Very concise C++ solution.


  • 0
    X
    void connect(TreeLinkNode *root) {
        if(!root)
            return;
            
        TreeLinkNode dummy(0);
        TreeLinkNode* toLink = &dummy;
        for(auto p = root; p; p = p->next){
            if(p->left){
                toLink->next = p->left;
                toLink = toLink->next;
            }
            if(p->right){
                toLink->next = p->right;
                toLink = toLink->next;
            }
        }
        
        connect(dummy.next);
    }

  • 0
    L

    The space is not constant. log(h) space.


  • 0
    X

    tail recursion can be converted to iterative methods easily; some compiler can even do it.


  • 0
    X
    void connect(TreeLinkNode *root) {
         while(root)
         {
             TreeLinkNode dummy(0);
             TreeLinkNode* toLink = &dummy;
              for(auto p = root; p; p = p->next){
                  if(p->left){
                      toLink->next = p->left;
                      toLink = toLink->next;
                  }
                  if(p->right){
                      toLink->next = p->right;
                      toLink = toLink->next;
                 }
            }
    
             root = dummy.next;
        }
    }

Log in to reply
 

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