题目
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

答案
level order traversal using the next pointer, update next pointers along the traversal

public class Solution {
    public void update_pointers(TreeLinkNode[] runners, TreeLinkNode ptr) {
        if(ptr != null) {
            if(runners[0] == null) runners[0] = ptr;
            else if(runners[1] == null) runners[0].next = runners[1] = ptr;
            else {
                runners[0] = runners[1].next = ptr;
                runners[1] = null;
            }
            if(runners[2] == null) runners[2] = ptr;
        }
    }
    
    public void connect(TreeLinkNode root) {
        TreeLinkNode curr;
        while(root != null) {
            curr = root;
            TreeLinkNode[] runners = {null, null, null};
            while(curr != null) {
                // Iterate through the level under curr
                update_pointers(runners, curr.left);
                update_pointers(runners, curr.right);                
                curr = curr.next;
            }
           
            root = runners[2];
        }
    }
}