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]]

1 public class Solution { 2         public ArrayList
      
       
        > zigzagLevelOrder(TreeNode root) { 3             ArrayList
        
         
          > res = new ArrayList
          
           
            >(); 4 if(root==null) return res; 5 LinkedList
            
              cur = new LinkedList
             
              (); 6 cur.offer(root); 7 int level = 0; 8 while(!cur.isEmpty()){ 9 LinkedList
              
                next = new LinkedList
               
                ();10 ArrayList
                
                  output = new ArrayList
                 
                  ();11 for(TreeNode n:cur){12 output.add(n.val);13 if(n.left!=null){14 next.offer(n.left);15 }16 if(n.right!=null){17 next.offer(n.right);18 }19 }20 if(level%2==1){21 Collections.reverse(output);22 }23 res.add(output);24 cur = next;25 level++;26 }27 return res;28 }29 }