Share another iterative solution with dummy node.


  • 0
    S

    I did not check all the shared solutions, so if this is know to you, just ignore it.

    The basic idea is still using three pointers to maintain the state:

    1. root is the head of the connected level

    2. dummy.next will store the head of next level

    3. cur is the tail of next level

    Steps:

    (1) In each round, we can use root and cur to build the next level.

    (2) At the end of each round, dummy.next is completely built, assign it to be next root.

    (3) Repeat (1)~(2) until the lowest level.

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

Log in to reply
 

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