Do you see a problem with below solution that does not require tracking prev node?
Iterative O(n) Space
class ConnectAllSiblings {
public static void connect(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0; i<size; i++) {
TreeNode curr = queue.remove();
if(curr.left!=null) {
queue.offer(curr.left);
}
if(curr.right!=null) {
queue.offer(curr.right);
}
curr.next = queue.peek();
}
}
}
Iterative O(1) space - this is not simpler but space efficient than the one in the course
class ConnectAllSiblings {
public static void connect(TreeNode root) {
TreeNode leftmostNode = root;
TreeNode prevRightmostNode = null;
while(leftmostNode!=null) {
TreeNode head = leftmostNode;
if(prevRightmostNode!=null) {
prevRightmostNode.next = head;
}
while(head!=null) {
if(head.left!=null) {
head.left.next = head.right;
}
if(head.next!=null) {
if(head.next.left!=null) {
if(head.right!=null) {
head.right.next = head.next.left;
} else if(head.left!=null) {
head.left.next = head.next.left;
}
} else if(head.next.right!=null) {
if(head.right!=null) {
head.right.next = head.next.right;
} else if(head.left!=null) {
head.left.next = head.next.right;
}
}
}
if(head.next==null) {
prevRightmostNode = head;
}
head = head.next;
}
leftmostNode = leftmostNode.left;
}
}