Populating Next Right Pointers in Each Node

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 to NULL.

Initially, all next pointers are set to NULL.

Note:

• 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).

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

Solution1: recursion
Use stack space

/**
 * 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) {
        if(root == null)
            return;
            
        if(root.left != null) {   
            root.left.next = root.right;  //connect 2 and 3
        }
        
        if(root.right != null && root.next != null) {
            root.right.next = root.next.left;  //connect 5 and 6
        }
        
        connect(root.left);
        connect(root.right);
    }
}

Solution2: iteration
这里每一层我们会维护成一个链表，这个链表其实就是每层起始的那个队列，因此我们只需要维护一个链表的起始指针就可以依次得到整个队列了。接下来就是有左加左入链表，有右加右入链表，知道链表没有元素了说明到达最底层了。算法的复杂度仍然是对每个结点访问一次，所以是run time complexity is O(n)，而空间上因为不需要额外空间来存储队列了，所以是space complexity is O(1)。

/**
 * 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) {
        if(root == null)
            return;
        
        TreeLinkNode lastHead = root;
        TreeLinkNode curHead = null;
        TreeLinkNode pre = null;
        
        while(lastHead != null) {
            TreeLinkNode lastCur = lastHead;
            while(lastCur != null) {
                if(lastCur.left != null) {
                    if(curHead == null) {
                        curHead = lastCur.left;
                        pre = curHead;
                    }else {
                        pre.next = lastCur.left;
                        pre = pre.next;
                    }
                }
                
                if(lastCur.right != null) {
                    if(curHead == null) {
                        curHead = lastCur.right;
                        pre = curHead;
                    }else {
                        pre.next = lastCur.right;
                        pre = pre.next;
                    }
                }
                lastCur = lastCur.next;
            }
            lastHead = curHead;
            curHead = null;
        }
    }
}