I wanted to solve the problem iteratively in Java. To do so, I am using two linked lists - one for the current level and one for the next level. I also keep track of the current level. Below is my program with the coments, if there is anything unclear please tell me.

```
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(root == null) return res;
List<TreeNode> curr = new LinkedList<TreeNode>();
curr.add(root);
int level = 0;
while(!curr.isEmpty()){
LinkedList<TreeNode> next = new LinkedList<TreeNode>(); //now next level is empty
LinkedList<Integer> toAdd = new LinkedList<Integer>(); //linked list of the intereg values
for(TreeNode node : curr){ //iterate throw the linked list of nodes in the current level
toAdd.add(node.val);
if(level%2 == 0){ //if I am at even level, then add first right child, then left child
if(node.right != null) next.add(node.right);
if(node.left != null) next.add(node.left);
}
else{ //if I am at odd level, then add first left child, then right child
if(node.left != null) next.add(node.left);
if(node.right != null) next.add(node.right);
}
}
level++; //increment level
res.add(new LinkedList<Integer>(toAdd)); //add current level
curr = next; //current level now points to the next level
}
return res;
}
```

I received thew Wrong Answer:

Input: {1,2,3,4,#,#,5}

Output: [[1],[3,2],[5,4]]

Expected: [[1],[3,2],[4,5]]

I don't see where is the problem in my logic?