C solution (9ms)


  • 0

    We do a level-by-level traversal. On each level, the parent pointer walks from left to right. On each walk, the parent points the previous child's next pointer to its children (if any, i.e left and/or right child). Initially the previous child pointer is set to a dummy node. This makes sure that the dummy node always points to the left most child in the level right below the parent.

    When we're done traversing the current level (i.e the inner while loop), we want to point our parent (left most) pointer to the leftmost child, in order to process the level below. This is achieved by resetting the left most parent pointer to the dummy node.

    void connect(struct TreeLinkNode *root) {
        if (!root) return;
        struct TreeLinkNode *parent, *child, *leftMostParent = root, dummy = {0};
        while (leftMostParent) {
            parent = leftMostParent;
            child = &dummy;
            while (parent) {
                if (parent->left) {
                    child->next = parent->left;
                    child = child->next;
                }
                if (parent->right) {
                    child->next = parent->right;
                    child = child->next;
                }
                parent = parent->next;
            }
            leftMostParent = dummy.next;
            dummy.next = NULL;
        }
    }
    

Log in to reply
 

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