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

116. Populating Next Right Pointers in Each Node

Notes 2020: requirement is to use O(1) space. Solution is to leverage next right pointers established at last level when dealing with current level

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

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

when visiting nodes from current level, connecting right pointers of next level

O(n) time and O(1) space

void connect(TreeLinkNode *root) {
        if (! root) {
            return;
        }
        
        TreeLinkNode* node = root;
        while (node->left) {
            TreeLinkNode* cur = node;
            while (cur) {
                cur->left->next = cur->right;
                if (cur->next) {
                    cur->right->next = cur->next->left;
                }
                cur = cur->next;
            }
            node = node->left;
        }
    }