C++ recursive solution, easy understanding


  • 8
    L
     void connect(TreeLinkNode *root) {
       if (!root) return;
        TreeLinkNode dummy(INT_MIN);
        for (TreeLinkNode *cur = root, *pre = &dummy; cur; cur = cur->next) {
            if (cur->left) {
                pre->next = cur->left;
                pre = pre->next;
            }
            if (cur->right) {
                pre->next = cur->right;
                pre = pre->next;
            }
        }
        connect(dummy.next);
    }

  • 0

    But the problem has to be solved with only constant extra space.


  • 0
    L

    I see, if in that case, you may can change the recursive call to a while loop as following

    void connect(TreeLinkNode *root) {
       if (!root) return;
        TreeLinkNode dummy(INT_MIN), *cur = root, *pre = &dummy;
        while (cur) {
            for ( pre = &dummy; cur; cur = cur->next) {
                if (cur->left) {
                    pre->next = cur->left;
                    pre = pre->next;
                }
                if (cur->right) {
                    pre->next = cur->right;
                    pre = pre->next;
                }
            }
            //connect(dummy.next);
            cur = dummy.next;
            dummy.next = nullptr;
       }
    

    }


  • 0
    A

    sorry, I cannot understand your code, given a binary tree like:

      1
     /    \
    
      2         3
    
     /  \           \
    

    4 5 6

    In the first for loop, dummy(pre)is pointed to 3,while dummy.next is NULL,how can we continue the next level?


Log in to reply
 

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