117. Populating Next Right Pointers in Each Node II - cocoder39/coco39_LC GitHub Wiki

117. Populating Next Right Pointers in Each Node II

dummy node

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        cur = root
        dummy = Node(0)
        while cur:
            prev = dummy
            while cur:
                if cur.left:    
                    prev.next = cur.left
                    prev = cur.left
                if cur.right:
                    prev.next = cur.right
                    prev = cur.right
                cur = cur.next
            if prev != dummy:
                cur = dummy.next
        return root

2 separate nodes to track

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        cur = root
        while cur:
            nextLevel = None
            prev = None
            while cur:
                if cur.left:    
                    if not nextLevel:
                        nextLevel = cur.left
                    if prev:
                        prev.next = cur.left
                    prev = cur.left
                if cur.right:
                    if not nextLevel:
                        nextLevel = cur.right
                    if prev:
                        prev.next = cur.right
                    prev = cur.right
                cur = cur.next
            cur = nextLevel
        return root

===========================

the tricky here is when visiting nodes from current level, you are not sure where the exactly position of nodes in next level since nodes in this level may have 0/1/2 child(ren).

O(n) time and O(1) space

void connect(TreeLinkNode *root) {
        TreeLinkNode dummy(0);
        TreeLinkNode* pre = &dummy;
        
        TreeLinkNode* cur = root;
        while (cur) {
            pre = &dummy;
            while (cur) {
                if (cur->left) {
                    pre->next = cur->left;
                    pre = cur->left;
                }
                if (cur->right) {
                    pre->next = cur->right;
                    pre = cur->right;
                }
                cur = cur->next;
            }
            if (pre != &dummy) {
                cur = dummy.next;
            }
        }
    }

follow up: link last of current level to begin of next level => still use pre node to handle it