Leetcode: Populating Next Right Pointers in Each Node II (java)

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Iterative Version from http://www.darrensunny.me/leetcode-populating-next-right-pointers-in-each-node-ii/

public void connect(TreeLinkNode root) {

        if (root == null)   // Empty tree

            return;

 

        TreeLinkNode headOfNextLevel = root;

 

        // Between levels

        while(headOfNextLevel != null) {

            // Initialize tailOfNextLevel and current

            TreeLinkNode tailOfNextLevel = null, current = headOfNextLevel;

            headOfNextLevel = null;

 

            // Within a level

            while(current != null) {

                // Update headOfNextLevel if we find the first node in the next level

                if (headOfNextLevel == null) {

                    if (current.left != null)

                        headOfNextLevel = current.left;

                    else if (current.right != null)

                        headOfNextLevel = current.right;

                }

 

                // Link its two subtrees if both exist

                if (current.left != null && current.right != null)

                    current.left.next = current.right;

 

                if (tailOfNextLevel != null) {

                    // Link the currently last node in the next level to a subtree (if any) of current node

                    if (current.left != null && current.right != null) {

                        tailOfNextLevel.next = current.left;

                        tailOfNextLevel = current.right;

                    } else if (current.left != null) {

                        tailOfNextLevel.next = current.left;

                        tailOfNextLevel = current.left;

                    } else if (current.right != null) {

                        tailOfNextLevel.next = current.right;

                        tailOfNextLevel = current.right;

                    }

                } else if (headOfNextLevel != null) {

                    // The first node in the next level has been found

                    if (headOfNextLevel.next != null)

                        tailOfNextLevel = headOfNextLevel.next;

                    else

                        tailOfNextLevel = headOfNextLevel;

                }

 

                // Move to the next node in the same level

                current = current.next;

            }

        }

    }

Read full article from Leetcode: Populating Next Right Pointers in Each Node II (java) - Muscler的专栏 - 博客频道 - CSDN.NET