117. Populating Next Right Pointers in Each Node II

Problem:

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

4/25/2018 update:
The best approach of all is to use dummy node on each level. Then we won't worry about the prev and next.

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        while (root != null) {
            TreeLinkNode childHead = new TreeLinkNode(0);
            TreeLinkNode child = childHead;
            while (root != null) {
                if (root.left != null) {
                    child.next = root.left;
                    child = root.left;
                }
                if (root.right != null) {
                    child.next = root.right;
                    child = root.right;
                }
                root = root.next;
            }
            root = childHead.next;
        }
    }
}

Analysis:
BFS, but queue is not allowed since constant space is required. Use 3 pointers, next, prev and root.

Solution:

 /**  
  * Definition for binary tree with next pointer.  
  * public class TreeLinkNode {  
  *   int val;  
  *   TreeLinkNode left, right, next;  
  *   TreeLinkNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public void connect(TreeLinkNode root) {  
    while (root != null) {  
      TreeLinkNode next = null; // next level's first node  
      TreeLinkNode prev = null; // current level's previous node  
      for (; root != null; root = root.next) {  
        if (next == null) next = (root.left != null) ? root.left : root.right;  
        if (root.left != null) {  
          if (prev != null) prev.next = root.left;  
          prev = root.left;  
        }  
        if (root.right != null) {  
          if (prev != null) prev.next = root.right;  
          prev = root.right;  
        }  
      }  
      root = next;  
    }  
   }  
 }