public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode level_start=root;
while(level_start!=null){
TreeLinkNode cur=level_start;
while(cur!=null){
if(cur.left!=null) cur.left.next=cur.right;
if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left;
cur=cur.next;
}
level_start=level_start.left;
}
}
}
Java solution with O(1) memory+ O(n) time



public void connect(TreeLinkNode root) { if(root == null) return; helper(root.left, root.right); } void helper(TreeLinkNode node1, TreeLinkNode node2){ if(node1 == null) return; node1.next = node2; helper(node1.left, node1.right); helper(node2.left, node2.right); helper(node1.right, node2.left); }


Javascript version:
var connect = function(root) { var level_start = root; while(level_start != null) { var cur = level_start; while(cur != null) { if(cur.left != null) cur.left.next = cur.right; if(cur.right != null && cur.next != null) cur.right.next = cur.next.left; cur = cur.next; } level_start = level_start.left; } };

public class Solution { public void connect(TreeLinkNode root) { // level order traversal while (root != null) { TreeLinkNode start = root; TreeLinkNode prev = null; // handle start.right.next = start.next.left while (start != null) { if (prev != null) { prev.next = start.left; } if (start.left != null) { start.left.next = start.right; } else { return; // since it is a perfect binary tree } prev = start.right; start = start.next; } root = root.left; } } }

TreeLinkNode root = new TreeLinkNode(1); root.left = new TreeLinkNode(2); root.right = new TreeLinkNode(3); root.left.right = new TreeLinkNode(5); root.right.left = new TreeLinkNode(6); root.right.right = new TreeLinkNode(7); root.left.right.left = new TreeLinkNode(8); root.left.right.right = new TreeLinkNode(9);
I think your answer is not correct,for example above. Your answer is 8>next is null,but I think the correct answer is 8>next is 9.
