Populating Next Right Pointers in Each Node II

Given a binary tree

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 toNULL.

Initially, all next pointers are set toNULL.

Note:

• You may only use constant extra space.

• Recursive approach is fine, implicit stack space does not count as extra space for this problem.

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

Note

和之前不一样的是，这里不一定是perfect树了，所以会跨左右孩子，右连右这种情况

需要另外记一个head（这一层的第一个）和pre（前一个节点），根据这些进行连接

Code

public void connect(TreeLinkNode root) {
    TreeLinkNode cur  = root;
    TreeLinkNode pre  = null;
    TreeLinkNode head = null;
    while (cur != null) {
        while (cur != null) {
            if (cur.left != null) {
                if (pre != null) {
                    pre.next = cur.left;
                } else 
                    head = cur.left; 
                pre = cur.left;
            }
            if (cur.right != null) {
                if (pre != null) {
                    pre.next = cur.right;
                } else 
                    head = cur.right; 
                pre = cur.right;   
            }
            cur = cur.next;
        }
        cur  = head;
        pre  = null;
        head = null;
    }
}