PopulatingNextRightPointersinEachNodeII.java

import java.util.ArrayList;
import java.util.List;

/**
 * Populating Next Right Pointers in Each Node IIOct 28 '12 Follow up for problem "Populating Next
 * Right Pointers in Each Node".
 *
 * <p>What if the given tree could be any binary tree? Would your previous solution still work?
 *
 * <p>Note:
 *
 * <p>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
 */
public class PopulatingNextRightPointersinEachNodeII {
  public void connect(TreeLinkNode root) {
    if (root == null) return;
    TreeLinkNode curLevel = root, cur = root;
    curLevel.next = null;
    List<TreeLinkNode> nextLevelNodes = new ArrayList<TreeLinkNode>();
    while (true) {
      while (cur != null) {
        if (cur.left != null) {
          nextLevelNodes.add(cur.left);
        }
        if (cur.right != null) {
          nextLevelNodes.add(cur.right);
        }
        cur = cur.next;
      }
      for (int i = 0; i < nextLevelNodes.size() - 1; i++) {
        nextLevelNodes.get(i).next = nextLevelNodes.get(i + 1);
      }
      if (nextLevelNodes.size() > 0) {
        curLevel = nextLevelNodes.get(0);
        cur = curLevel;
        nextLevelNodes.clear();
      } else {
        break;
      }
    }
  }
}