Populating Next Right Pointers in Each Node II

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

Solution1: recursion

/**
 * 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) {
            if(root.right != null)   //如果右子树不为空，左子树连右子树
                root.left.next = root.right;
            else {
                TreeLinkNode p = root.next;
                while(p != null && p.left == null && p.right == null) {   //如果左右子树为空，找下一个有子树的node
                    p = p.next;
                }
                if(p != null) {
                    if(p.left != null) {
                        root.left.next = p.left;
                    }else if(p.left == null && p.right != null) {
                        root.left.next = p.right;
                    }
                }
            }
        }
        
        if(root.right != null) {
            TreeLinkNode p = root.next;
            while(p != null && p.left == null && p.right == null) {
                    p = p.next;
            }
            if(p != null) {
                if(p.left != null) {
                    root.right.next = p.left;
                }else if(p.left == null && p.right != null) {
                    root.right.next = p.right;
                }
            }
        }

        connect(root.right);
        connect(root.left);
    }
}

Solution2: iteration. 横着连就是 level order traversal. 通常使用BFS，但是题目中每个node自带next指针，相当于就是自带Queue了。所以，从上向下一层一层的连接即可。 每层： a. 记录下一层的开始点 b. 连接各个Nodes.
时间复杂度和空间复杂度不变，还是O(n)和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;
        
        while(root != null) {
            TreeLinkNode levelStart = null;
            TreeLinkNode pre = null;
            for(; root != null; root = root.next) {
                if(levelStart == null) {
                    if(root.left != null)
                        levelStart = root.left;
                    else if(root.left == null && root.right != null)
                        levelStart = root.right;
                }
                
                if(root.left != null) {
                    if(pre != null) 
                        pre.next = root.left;
                    pre = root.left;
                }
                if(root.right != null) {
                    if(pre != null)
                        pre.next = root.right;
                    pre = root.right;
                }
            }
            root = levelStart;
        }
    }
}