# Concise Java Solution; BFS; With Comments

• Time complexity: O(n), space complexity: O(n)

``````public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null){
return res;
}
//Indicate the level
int zig = 1;
//Record size of current level
int count = 0;
TreeNode cur;
while(queue.size()>0){
List<Integer> temp = new ArrayList<Integer>();
count = queue.size();

for(int i = 0; i < count; i++){
cur = queue.remove();
if(zig % 2 == 0){
}else{
}
if(cur.left != null){
}
if(cur.right != null){
}
}

zig++;
}
return res;
}
}``````

• ``````public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) return ret;
Deque<TreeNode> q = new ArrayDeque<TreeNode>();
int dir = 1;
while(!q.isEmpty()){
int qsize = q.size();

List<Integer> level = new ArrayList<Integer>();
for (int i=0;i<qsize;++i){
TreeNode t = q.removeFirst();
if (dir == 1){