PopulatingNextRightPointersinEachNode.java

/**
 * Given a binary tree
 *
 * <p>struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate
 * each next pointer to point to its next right node. If there is no next right node, the next
 * pointer should be set to NULL.
 *
 * <p>Initially, all next pointers are set to NULL.
 *
 * <p>Note:
 *
 * <p>You may only use constant extra space. You may assume that it is a perfect binary tree (ie,
 * all leaves are at the same level, and every parent has two children).
 *
 * <p>For example, Given the following perfect binary tree, 1 / \ 2 3 / \ / \ 4 5 6 7 After calling
 * your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
 */
public class PopulatingNextRightPointersinEachNode {
  public void connect(TreeLinkNode root) {
    if (root == null) return;
    TreeLinkNode curLevel = root;
    TreeLinkNode cur = root;
    curLevel.next = null;
    while (true) {
      while (cur != null) {
        if (cur.left != null) {
          cur.left.next = cur.right;
          if (cur.next != null) {
            cur.right.next = cur.next.left;
          }
        }
        cur = cur.next;
      }
      if (curLevel.left != null) {
        curLevel = curLevel.left;
        cur = curLevel;
      } else {
        break;
      }
    }
  }
}