103. Binary Tree Zigzag Level Order Traversal Leetcode Java

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution:

Similar to the level order traversal. In the solution of level order traversal, I use a queue of linked list as the data structure, first in first out to realize the traversal from left to right for each level. For this problem, I use double-ended queue as the data structure, for odd level, remove the element from the head, and add its children(order: left, right) to the tail. While for even level, remove element from the tail, and add its children(order: right, left) to the head. The deque looks like: 

1st level remove the head [3] =>[] ; res:{[3]} then, add its children to the tail one by one from left to right : Head,[9 20],tail; 

2nd level remove the tail [9,20]  => [9] ;res:{[3],[20]}, add its children to the head from right to left, [9]=>[15,7,9]. Remove the tail again [15,7,9]=>[15,7], res:{[3],[20,9]},

3rd level remove the head[15,7]=>[7]; res:{[3],[20,9],[15]}, 15 doesn't have any children. remove the head [7]=>[]; res:{[3],[20,9],[15,7]} 7 doesn't have any children.

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(root==null) return res;  
    List<Integer> items=new ArrayList<Integer>();  
    LinkedList<TreeNode> q=new LinkedList<TreeNode>();  
    q.add(root);  
    int level=1;  
    int lastL=1;  
    int curL=0;  
    while(!q.isEmpty()){  
      if(level%2==1){  
        TreeNode cur=q.removeFirst();  
        lastL--;  
        items.add(cur.val);  
        if(cur.left!=null){  
          q.add(cur.left);  
          curL++;  
        }  
        if(cur.right!=null){  
          q.add(cur.right);  
          curL++;  
        }  
      }  
      else{  
        TreeNode cur=q.removeLast();  
        lastL--;  
        items.add(cur.val);  
        if(cur.right!=null){  
          q.addFirst(cur.right);  
          curL++;  
        }  
        if(cur.left!=null){  
          q.addFirst(cur.left);  
          curL++;  
        }  
      }  
      if(lastL==0){  
        res.add(items);  
        items=new ArrayList<Integer>();  
        lastL=curL;  
        curL=0;  
        level++;  
      }  
    }  
    return res;  
   }