Binary Tree Zigzag Level Order Traversal @LeetCode

package Level4;  
  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.LinkedList;  
import java.util.Queue;  
  
import Utility.TreeNode;  
  
/** 
 * Binary Tree Zigzag Level Order Traversal 
 *  
 * 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] 
] 
confused what "{1,#,2,3}" means  > read more on how binary tree is serialized on OJ. 


OJ's Binary Tree Serialization: 
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below. 

Here's an example: 
   1 
  / \ 
 2   3 
    / 
   4 
    \ 
     5 
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}". 
 */  
public class S103 {  
  
    public static void main(String[] args) {  
  
    }  
  
    public ArrayList> zigzagLevelOrder(TreeNode root) {  
        ArrayList





> ret = new ArrayList>();  
        if(root == null){  
            return ret;  
        }  
          
        Queue queue = new LinkedList();  
        ArrayList al = new ArrayList();  
        queue.add(root);  
        int currentLevel = 1;  
        int nextLevel = 0;  
        boolean left = true;  
          
        while(!queue.isEmpty()){  
            TreeNode cur = queue.remove();  
            currentLevel--;  
            al.add(cur.val);  
            if(cur.left != null){  
                queue.add(cur.left);  
                nextLevel++;  
            }  
            if(cur.right!=null){  
                queue.add(cur.right);  
                nextLevel++;  
            }  
              
            if(currentLevel == 0){  
                if(!left){          // 当自右往左时，要翻转al  
                    Collections.reverse(al);  
                }  
                left = !left;  
                ret.add(al);  
                al = new ArrayList();  
                currentLevel = nextLevel;  
                nextLevel = 0;  
            }  
        }  
        return ret;  
    }  
}